时间和空间复杂度的计算

Question

我正在解决这个Leetcode问题-“给定一个包含2-9 (包括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

任何关于计算此解决方案的时间和空间复杂度的帮助或解释都将是有帮助的。谢谢。

Answer 1

对于某些组合问题，时间和空间复杂性可能由输出的大小决定。查看循环和函数调用，在函数中所做的工作是一个字符串连接和一个附加输出的每个元素。还有多达4次对self.letterCombinations(digits[1:])的重复递归调用:假设这些调用没有被缓存，我们需要添加额外的重复工作。

当len(digits) == n时，我们可以写出解决问题所需的运算次数的公式。如果T(n)是步数，A(n)是答案数组的长度，我们得到T(n) = 4*T(n-1) + n*A(n) + O(1)。我们在A(n)上得到一个额外的n乘法因子，因为字符串连接是线性时间；使用列表和str.join()的实现可以避免这种情况。

由于A( n )是4^n的上界，而T(1)是一个常数，这就给出了T(n) = O(n * (4^n))；这里的空间复杂度也是O(n * (4^n))，给定长度为n的4^n个字符串。

复杂性分析的一个可能令人困惑的部分是，除非另有说明，否则它通常是最坏的情况分析。这就是为什么我们在这里使用4而不是3的原因:如果任何输入可以给出4^n个结果，我们就使用这个数字，即使许多数字输入会给出更接近3^n的结果。