Анализ двух-двух алгоритмов Big-O

Question

Я создал два решения для leetcode problem 17, в которых он просит вас генерировать все возможные текстовые строки из комбинации номеров телефонов, например. "3" Результаты ["d","e","f"].

Моего первое решения использует рекурсивный алгоритм для генерации строк и приводится ниже:

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

Я немного ржавый с большим-O, но мне кажется, что сложность пространства будет O(n) для рекурсивный вызов, т. е. его максимальная глубина, O(n) для строки буфера и O(n*c^n) для полученных строк. Будет ли эта сумма вместе как O(n+n*c^n)?

Для временной сложности я немного смущен. Каждый уровень рекурсии выполняет c подталкивает + попс + рекурсивные вызовы, умноженные на количество операций на следующем уровне, поэтому это звучит как c^1 + c^2 + ... + c^n. Кроме того, есть c^n дублирования строк длины n. Как объединить это в приятное представление большой-O?

---

Второе решение рассматривает ряд результатов, как смешанное число натальной и преобразует его в строку, как вы могли бы выполнить Int в шестнадцатеричной строки преобразования:

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

В этом случае, я считают, что сложность пространства равна O(n*c^n), аналогичной первому решению, минус буфер и рекурсия, а временная сложность должна быть O(n) для первого цикла цикла и дополнительного O(n*c^n) для создания результирующей строки для каждого из возможных результатов. Окончательный большой-O для этого O(n+n*c^n). Правильно ли мой процесс размышлений?

---

Edit: Чтобы добавить некоторые пояснения к коду, представьте входную строку "234". Первое рекурсивное решение вызовет generate_strings с аргументами (0, "234", lut, r, work). lut - это таблица поиска, которая преобразует число в соответствующие символы. r - вектор, содержащий результирующие строки. work - это буфер, в котором выполняется работа.

Первый рекурсивный вызов будет видеть, что индекс 0 цифра 2 что соответствует "abc", нажмите a к work, а затем вызвать generate_strings с аргументами (1, "234", lut, r, work). Как только звонок вернется, он будет толкать b на work и промыть и повторить.

Когда index равен размеру digits, тогда была создана уникальная строка, а строка нажимается на r.

---

Для второго решения входная строка сначала преобразуется из своего представления ascii в его целочисленное представление. Например, "234" преобразуется в "\x02\x03\x04".Затем код использует их как индексы для поиска количества соответствующих символов в таблице поиска и вычисляет общее количество строк, которые будут в результате. например если входная строка была "234", 2 соответствует abc, которая имеет 3 символа. 3 соответствует def, который имеет 3 символа. 4 соответствует ghi, который имеет 3 символа. Общее количество возможных строк: 3*3*3 = 27.

Затем код использует счетчик для представления каждой из возможных строк. Если i были 15, это было бы оценено при первом нахождении 15 % 3, которое равно 0, что соответствует первому символу для первой цифры (a). Затем разделите 15 на 3, который равен 5. 5 % 3 - 2, который соответствует третьему символу для второй цифры, которая равна f. Наконец разделите 5 на 3, и вы получите 1. 1 % 3 - 1, который соответствует второму символу для третьей цифры, h. Поэтому строка, соответствующая номеру 15, равна afh. Это выполняется для каждого числа, и полученные строки сохраняются в r.

Answer 1

Рекурсивный алгоритм:

пространства: каждый уровень рекурсии представляет собой О (1), и есть O (N) уровни. Таким образом, для рекурсии O (n). Пространством результата является O (c^n), где c = max (lut [i] .length). Общее пространство для алгоритма O (c^n).

Время: пусть T (n) будет стоить для цифры с длиной n. Тогда мы имеем рекуррентную формулу: T (n) < = c T (n-1) + O (1). Решите это уравнение, получив T (n) = O (c^n).

алгоритм хэширования:

Space: если вам нужно место для хранения всех результатов, то он по-прежнему O (с^п).

Время: O (n + c^n) = O (c^n).

---

Мне нравится алгоритм HASHING, потому что это лучше, если вопрос просит вас дать конкретный результат строки (предположим, мы заказываем их алфавитном порядке). В этом случае пространство и время есть только O (n).

Этот вопрос напоминает мне аналогичный вопрос: сгенерируйте все перестановки множества {1,2,3, ..., n}. Хеширующий подход лучше, потому что, создавая перестановку один за другим и обрабатывая его, мы можем сэкономить много места.