Analiza dwóch algorytmów Big-O

Question

Stworzyłem dwa rozwiązania dla leetcode problem 17, w których prosi się o wygenerowanie wszystkich możliwych ciągów tekstowych z kombinacji numerów telefonów, np. "3" wyniki w ["d","e","f"].

Moje pierwsze rozwiązanie wykorzystuje algorytm rekurencyjny do generowania ciągów i jest podany poniżej:

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; 
    } 
}; 

jestem trochę zardzewiały z big-O, ale wydaje mi się, że złożoność przestrzeń byłaby O(n) dla wywołanie rekurencyjne, tj. jego maksymalna głębokość, O(n) dla ciągu bufora i O(n*c^n) dla wynikowych ciągów. Czy to suma razem jako O(n+n*c^n)?

Dla złożoności czasowej jestem nieco zdezorientowany. Każdy poziom rekursji wykonuje c pcha + pops + rekursywne połączenia pomnożone przez liczbę operacji przez następny poziom, więc brzmi to jak c^1 + c^2 + ... + c^n. Ponadto istnieją duplikaty długości c^n z n. Jak mogę to skonsolidować w ładne reprezentacje?

---

Drugie rozwiązanie postrzega liczbę wyników jako mieszany liczby radix i konwertuje go na sznurku, jak można wykonać int na hex konwersji strun:

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; 
    } 
}; 

W tym przypadku, sądzi, że złożoność przestrzeni jest równa O(n*c^n) podobna do pierwszego rozwiązania bez bufora i rekurencji, a złożoność czasu musi wynosić O(n) dla pierwszej pętli for i dodatkowej O(n*c^n), aby utworzyć ciąg wyniku dla każdego z możliwych wyników. Ostatecznym big-O dla tego jest O(n+n*c^n). Czy mój proces myślowy jest poprawny?

---

Edit: dodać kilka wyjaśnień do kodu, wyobrazić ciąg wejściowy "234". Pierwsze rozwiązanie rekurencyjne wywoła generate_strings z argumentami (0, "234", lut, r, work). lut to tabela przeglądowa, która konwertuje liczbę na odpowiadające jej znaki. r to wektor zawierający wynikowe ciągi. work to bufor, w którym wykonywana jest praca.

Pierwsze wywołanie rekurencyjne wtedy zobaczyć, że cyfrowy wskaźnik 0 jest 2 który odpowiada "abc" wcisnąć a do work, a następnie zadzwonić generate_strings z argumentami (1, "234", lut, r, work). Po otrzymaniu połączenia urządzenie zostanie następnie przepchnięte b do work, a następnie spłucz i powtórz.

Gdy index jest równy rozmiarowi digits, generowany jest unikalny ciąg znaków, a ciąg znaków jest przesyłany do r.

---

Dla drugiego rozwiązania, ciąg wejściowy jest najpierw konwertowany z reprezentacji ASCII na jego całkowitą reprezentację. Na przykład "234" jest konwertowane na "\x02\x03\x04".Następnie kod wykorzystuje je jako indeksy do wyszukania liczby odpowiednich znaków w tablicy odnośników i oblicza całkowitą liczbę łańcuchów, które będą w wyniku. na przykład jeśli ciąg wejściowy to "234", 2 odpowiada , który ma 3 znaki. 3 odpowiada def, który ma 3 znaki. 4 odpowiada ghi, który ma 3 znaki. Całkowita liczba możliwych łańcuchów to 3*3*3 = 27.

Następnie kod wykorzystuje licznik do reprezentowania każdego z możliwych ciągów. Jeśli i byłby 15, byłby oceniany przez najpierw znalezienie 15 % 3, który jest 0, odpowiadający pierwszemu znakowi dla pierwszej cyfry (a). Następnie podziel 15 przez 3, który jest 5. 5 % 3 to 2, który odpowiada trzeciemu znakowi drugiej cyfry, który jest f. Na koniec podziel 5 przez 3, a otrzymasz 1. 1 % 3 to 1, który odpowiada drugiemu znakowi trzeciej cyfry, h. Dlatego ciąg znaków odpowiadający numerowi 15 jest afh. Jest to wykonywane dla każdego numeru, a otrzymane łańcuchy są przechowywane w r.

Answer 1

rekurencyjny algorytm:

Miejsce: każdy poziom rekurencji O (1) i nie jest O (n) w surowicy. Zatem jest to O (n) dla rekursji. Przestrzeń wyniku to O (c^n), gdzie c = max (lut [i] .length). Całkowita przestrzeń dla algorytmu to O (c^n).

Czas: Niech T (n) będzie kosztem cyfry o długości n. Następnie mamy formułę rekursji: T (n) < = c T (n-1) + O (1). Rozwiąż to równanie dając T (n) = O (c^n).

Wymieszanie Algorytm:

Miejsce: jeśli potrzebna jest przestrzeń do przechowywania wszystkich wyników, to jednak O (C^N).

Czas: O (n + c^n) = O (c^n).

---

Lubię algorytmu mieszaja ponieważ jest lepiej jeśli pytanie prosi, aby dać konkretny rezultat string (załóżmy, że zamówić je w kolejności alfabetycznej kolejności). W takim przypadku przestrzeń i czas to tylko O ​​(n).

To pytanie przypomina mi podobne pytanie: wygeneruj wszystkie permutacje zestawu {1,2,3, ..., n}. Podejście haszowania jest lepsze, ponieważ generując permutację jeden po drugim i przetwarzając je, możemy zaoszczędzić dużo miejsca.