Сложность времени для рекурсивного алгоритма отображения цифр на буквы, стиль клавиатуры телефона

Question

Следующий код возвращает все возможные последовательности букв, которые может представлять последовательность цифр, с помощью клавиатуры телефона для сопоставления цифр и букв, как показано на следующем рисунке.

Вот несколько примеров входов и выходов:

Вход: "2"
Выход: ["a", "b", "c"]

Ввод: "23"
Ввод: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Если n - это количество цифр на входе, а k - максимальное количество символов, сопоставленных с отдельной цифрой, какова будет сложность времени?

У меня естьпридумайте следующее рекуррентное соотношение (поправьте меня, если я ошибаюсь): T(n) = T(n-1) + k^(n-1) * k

Но я не могу понять сложность времени.Может ли кто-нибудь помочь мне понять, как рассчитать временную сложность этого типа решения?

class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }
        Map<Integer, List<Character>> map = new HashMap<>();
        map.put(2, Arrays.asList('a','b','c'));
        map.put(3, Arrays.asList('d','e','f'));
        map.put(4, Arrays.asList('g','h','i'));
        map.put(5, Arrays.asList('j','k','l'));
        map.put(6, Arrays.asList('m','n','o'));
        map.put(7, Arrays.asList('p','q','r','s'));
        map.put(8, Arrays.asList('t','u','v'));
        map.put(9, Arrays.asList('w','x','y','z'));

        List<String> result = new ArrayList<>();
        recurse(digits, result,"", map, 0);
        return result;
    }

    public void recurse(String digits, List<String> result, String temp, Map<Integer, List<Character>> map, int index) {
        if(index == digits.length()) {
            result.add(temp);
        } else {            
            Integer ch = Character.getNumericValue(digits.charAt(index));
            List<Character> chars = map.get(ch);
            for(int i=0; i < chars.size(); i++) {
                recurse(digits, result, temp + chars.get(i), map, index + 1);
            }
        }
    }
}

Answer 1

Сложность в обозначении Big-O равна O(4^n).

Это не точно , что вы просили - вы спрашивали о сложности времени - но Big-O - обычное явлениеспособ выразить это.

Обратите внимание, что я вообще не использовал k - это потому, что k варьируется в зависимости от точного состава вашей входной строки, а Big-O занимает наихудшее время выполнения(что в вашем случае, если все цифры сопоставлены с четырьмя разными буквами).

Если вы хотите использовать k, вы можете сделать это:

O(k1^n1 * k2^n2 * k3^n3 ...)

Где k1 - это конкретное значение k, а n1 - это числоцифры во входной строке, которые соответствуют этому значению k.В вашем примере будут только k1=3 и k2=4, так как другие значения k невозможны: O(3^n1 * 4^n2)

Answer 2

Один из способов найти временную сложность для перечислительных алгоритмов, подобных этому (где вы соберете все способы что-то сделать), состоит в том, чтобы подумать о том, сколько существует выходных данных и сколько времени требуется для вычисления выходных данных.

Если у вас есть n символов, каждый из которых соответствует k параметрам, то число возможных результатов будет k^n.Следовательно, сложность вашего алгоритма составляет , по крайней мере, k^n или Omega(k^n), поскольку перечисляются O(k^n) выходных данных.

Нам все еще нужно рассмотреть, сколько времени требуется для вычисления каждоговход.Обратите внимание, что вы строите String длины n, добавляя по одному символу за раз.Поскольку String s являются неизменяемыми, каждый раз, когда вы добавляете персонажа, должен быть создан совершенно новый String.Работа по созданию String длины n путем добавления символов составляет 1 + 2 + ... + n = O(n^2).

К счастью, работа по созданию результата одинакова для всех результатов.Поэтому мы можем просто умножить количество результатов на работу для каждого результата, чтобы получить конечную сложность O(n^2 * k^n) или, более конкретно, Theta(n^2 * k^n).

---

Мы также можем получить повторениеотношение следующим образом.Пусть i будет таким же, как index в вашем коде, что составляет от 0 до n.Пусть j будет n-i, что означает «количество цифр, оставшихся для обработки».

Тогда у нас есть T(j) = k*((i+1) + T(j-1)) = k*((n-j+1) + T(j-1)) и T(0) = 1.Общая сложность времени определяется как T(j), где j=n.

Объяснение: Предположим, у вас осталось j цифр для обработки, что соответствует одному вызову recurse.Нам нужно перебрать k символов, и на каждой итерации этого цикла мы выполняем i+1 работы (чтобы добавить символ к temp), а также T(j-1) работы (для рекурсии, имея наименьшее количество оставшихся цифр).для обработки).

Если мы "развернем" рецидив, мы найдем:

T(n) = k*(1 + T(n-1))
     = k*(1 + k*(2 + T(n-2)))
     = k*(1 + k*(2 + k*(3 + ... k*(n + 1)...)))
     = 1*k + 2*k^2 + 3*k^3 + ... + n*k^n + 1*k^n

Затем нам нужно ограничить верхнюю и нижнюю границу этой суммы.

T(n) <= 1*k^n + 2*k^n + ... + n*k^n + 1*k^n
      = (1 + 2 + ... + n)*k^n + 1*k^n
      = O(n^2 * k^n)

Нижняя граница сложнее.Пусть a будет любой константой с 0 < a < 1.Пусть m = floor(a * n).

T(n) >= m*k^m + (m+1)*k^(m+1) + ... + n*k^n    (there are n-m+1 terms)
     >= (n-m+1) * m*k^m                        (replace each term with m*k^m)
      = (constant*n) * (a*n)*k^(a*n)
      = constant * n^2 * k^(a*n)

Это означает, что для любой константы 0 < a < 1 мы имеем T(n) = Omega(n^2 * k^(a*n)), поэтому мы можем доказать, что наша нижняя оценка для T(n) произвольно близка к Omega(n^2 * k^n).

В сочетании с верхней границей мы показали, что T(n) = Theta(n^2 * k^n).

Answer 3

На мой взгляд, это так же просто, как:

, если N = digits.length, и k = number of letters for this button, то k*N, поэтому O(kN).