İki algoritmanın Big-O analizi

Question

leetcode problem 17 için iki çözüm oluşturdum; bir telefon numarası kombinasyonundan olası tüm metin dizelerini oluşturmanızı ister. "3", ["d","e","f"] sonuçlarıyla sonuçlanır.

Benim ilk çözüm dizeleri oluşturmak için bir özyinelemeli bir algoritma kullanır ve aşağıda verilmiştir:

class Solution { 
public: 
    void fill_LUT(vector<string>& lut) { 
     lut.clear(); 
     lut.push_back(" "); 
     lut.push_back(""); 
     lut.push_back("abc"); 
     lut.push_back("def"); 
     lut.push_back("ghi"); 
     lut.push_back("jkl"); 
     lut.push_back("mno"); 
     lut.push_back("pqrs"); 
     lut.push_back("tuv"); 
     lut.push_back("wxyz"); 
    } 

    void generate_strings(int index, string& digits, vector<string>& lut, vector<string>& r, string& work) { 
     if(index >= digits.size()) { 
      r.push_back(work); 
      return; 
     } 

     char idx = digits[index] - '0'; 
     for(char c : lut[idx]) { 
      work.push_back(c); 
      generate_strings(index+1, digits, lut, r, work); 
      work.pop_back(); 
     } 
    } 

    vector<string> letterCombinations(string digits) { 
     vector<string> r; 
     vector<string> lut; 
     fill_LUT(lut); 

     if(digits.size() <= 0) 
      return r; 

     string work; 
     generate_strings(0, digits, lut, r, work); 

     return r; 
    } 
}; 

Ben büyük-O ile biraz paslı değilim, ama uzay karmaşıklığı için O(n) olacağını bana görünen Yinelemeli çağrı, yani maksimum derinliği, tampon dizisi için O(n) ve sonuçtaki dizeler için O(n*c^n). Bu O(n+n*c^n) olarak toplanır mı?

Zaman karmaşıklığı için biraz kafam karıştı. Yinelemenin her seviyesi c ibaresi + pops + tekrar aramaları bir sonraki seviyeye kadar işlem sayısı ile çarparak gerçekleştirir, böylece c^1 + c^2 + ... + c^n gibi görünür. Ayrıca, c^nn uzunluk dizgilerinin kopyaları vardır. Bunu güzel bir büyük-O sunumuna nasıl katlarım?

---

ikinci çözüm karışık sayı tabanı numarası olarak sonuç sayısını görür ve onaltılık dize dönüştürme için bir int performans gösterebileceği gibi bir dizeye dönüştürür:

class Solution { 
public: 
    void fill_LUT(vector<string>& lut) { 
     lut.clear(); 
     lut.push_back(" "); 
     lut.push_back(""); 
     lut.push_back("abc"); 
     lut.push_back("def"); 
     lut.push_back("ghi"); 
     lut.push_back("jkl"); 
     lut.push_back("mno"); 
     lut.push_back("pqrs"); 
     lut.push_back("tuv"); 
     lut.push_back("wxyz"); 
    } 

    vector<string> letterCombinations(string digits) { 
     vector<string> r; 
     vector<string> lut; 
     fill_LUT(lut); 

     if(digits.size() <= 0) 
      return r; 

     unsigned total = 1; 
     for(int i = 0; i < digits.size(); i++) { 
      digits[i] = digits[i]-'0'; 
      auto m = lut[digits[i]].size(); 
      if(m > 0) total *= m; 
     } 

     for(int i = 0; i < total; i++) { 
      int current = i; 
      r.push_back(string()); 
      string& s = r.back(); 
      for(char c : digits) { 
       int radix = lut[c].size(); 
       if(radix != 0) { 
        s.push_back(lut[c][current % radix]); 
        current = current/radix; 
       } 
      } 
     } 

     return r; 
    } 
}; 

Bu durumda ben uzay karmaşasının, ilk çözümün tampon ve özyinelemesine benzer şekilde O(n*c^n) olduğuna ve zaman karmaşıklığının, ilk döngü için O(n) ve olası sonuçların her biri için bir sonuç dizesi oluşturmak üzere ek bir O(n*c^n) olması gerektiğine inanıyoruz. Bunun için son büyük-O O(n+n*c^n). Düşünce sürecim doğru mu?

---

Düzenleme:, koda bazı konulara açıklık eklemek "234" bir giriş dizesi hayal etmek. İlk özyinelemeli çözüm (0, "234", lut, r, work) argümanlarıyla generate_strings'u arayacaktır. lut, bir sayıyı karşılık gelen karakterlere dönüştüren bir görünüm tablosudur. r, sonuçtaki dizeleri içeren vektördür. work, çalışmanın gerçekleştirildiği bir arabellektir.

ilk özyinelemeli çağrı ardından endeks 0 haneli "abc" ile karşılık 2 olduğunu, work için a itmek olduğunu gördükten sonra argümanları (1, "234", lut, r, work) ile generate_strings arayacak. Çağrı geri döndüğünde, b'u work'a gönderir ve durulayıp tekrar eder.

index, digits boyutuna eşit olduğunda, benzersiz bir dize oluşturuldu ve dize r'a aktarıldı. İkinci çözüm için

---

, girdi dizisi birinci tamsayı temsil var için bu ASCII temsil var dönüştürülür. Örneğin "234", "\x02\x03\x04"'a dönüştürülür.Ardından kod, arama tablosundaki karşılık gelen karakterlerin sayısını aramak için dizinler olarak kullanır ve sonuçta kullanılacak toplam dizge sayısını hesaplar. Örneğin. Giriş dizgisi "234" ise, 2, 3 karakterden oluşan abc ile karşılık gelir. 3, 3 karakterden oluşan def ile karşılık gelir. 4, 3 karakterden oluşan ghi ile karşılık gelir. Toplam olası dizi sayısı 3*3*3 = 27. Daha sonra kod, olası dizelerin her birini temsil etmek için bir sayaç kullanır. i, 15 ise, ilk rakamın ( a) birinci karakteri ile karşılık gelen 0 olan 15 % 3'u bulmak suretiyle değerlendirilir. Daha sonra 15'u 3 ile 5 arasına bölün. 5 % 3, f olan ikinci hane için üçüncü karaktere karşılık gelen 2 şeklindedir. Son olarak 3 tarafından 5'u bölün ve 1 elde edersiniz. 1 % 3, h üçüncü rakamı için ikinci karaktere karşılık gelen 1'dur. Bu nedenle, 15 numaralı numaraya karşılık gelen dize afh'dur. Bu her sayı için gerçekleştirilir ve sonuç dizeleri r'da depolanır.

Answer 1

Tekrar Meydana Gelen algoritim:

alan yineleme her düzeyde O olduğu (1) ve O (n) seviyeleri bulunmaktadır. Böylece özyineleme için O (n) 'dir. Sonuç alanı O (c^n) 'dir, burada c = maks (lut [i] .length). Algoritma için toplam alan O (c^n) 'dir.

Süre: T (n) n uzunluğundaki rakamın maliyeti olsun. Daha sonra tekrarlama formülü vardır: T (n) < = c T (n-1) + O (1). Bu denklemi çözün T (n) = O (c^n).

Çırpı algoritması:

Alanı: tüm sonuçları saklamak için yer ihtiyacı varsa, o zaman O (c^n) hala.

Süre: O (n + c^n) = O (c^n). soru (biz alfabe sırasına göre bunları sipariş varsayalım) Belirli bir dize sonucunu vermek ister eğer o iyi olduğu için

---

Ben Özetleme algoritması gibi. Bu durumda, uzay ve zaman sadece O (n) dir.

Bu soru, benzer bir soruya beni hatırlatıyor: setin tüm permütasyonlarını oluşturmak {1,2,3, ..., n}. Karma yaklaşımı daha iyidir çünkü permütasyonu tek tek üretip işleyerek çok fazla yer tasarrufu sağlayabiliriz.