Блог

Я работаю над этой проблемой с кодом — «Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке.

Ниже приведено сопоставление цифр с буквами (точно так же, как на телефонных кнопках). Обратите внимание, что 1 не сопоставляется ни с какими буквами».

Это рекурсивное решение проблемы, которое я смог понять, но я не в состоянии понять временную и пространственную сложность решения.

 if not len(digits):
        return []
    
    res = []
    
    my_dict = {
        '2':'abc',
        '3':'def',
        '4':'ghi',
        '5':'jkl',
        '6':'mno',
        '7':'pqrs',
        '8':'tuv',
        '9':'wxyz'
    }
    
    if len(digits) == 1:
        return list(my_dict[digits[0]])
    
    my_list = my_dict[digits[0]] #string - abc
    
    for i in range(len(my_list)): # i = 0,1,2
        for item in self.letterCombinations(digits[1:]):
            print(item)
            res.append(my_list[i]   item) 
    return res
 

Любая помощь или объяснение, касающиеся расчета сложности времени и пространства для этого решения, были бы полезны. Спасибо.

При определенных комбинаторных задачах сложность во времени и пространстве может зависеть от размера выходных данных. Если посмотреть на циклы и вызовы функций, то работа, выполняемая в функции, представляет собой объединение одной строки и одно добавление для каждого элемента вывода. Существует также до 4 повторяющихся рекурсивных вызовов self.letterCombinations(digits[1:]) : предполагая, что они не кэшируются, нам нужно добавить дополнительную повторяющуюся работу, выполняемую там.

Мы можем написать формулу для количества операций, необходимых для решения проблемы, когда len(digits) == n . Если T(n) — количество шагов, а A(n) — длина массива ответов, мы получим T(n) = 4*T(n-1) n*A(n) O(1) . Мы получаем дополнительный мультипликативный коэффициент n на A(n), потому что объединение строк-это линейное время; реализация со списками и str.join() позволит избежать этого.

Поскольку A(n) ограничено сверху 4^n, а T(1) является константой, это дает T(n) = O(n * (4^n)) ; сложность пространства здесь также O(n * (4^n)) , учитывая 4^n строк длины n.

Одна из возможных запутывающих частей анализа сложности заключается в том, что обычно это анализ наихудшего случая, если не указано иное. Вот почему мы используем здесь 4 вместо 3: если какой-либо ввод может дать 4^n результатов, мы используем эту цифру, хотя многие цифровые вводы дали бы результаты ближе к 3^n.