Python-如何计算递归函数的时间复杂性？

Question

我想用尽可能多的方法解决塔式料斗问题，并计算每种方法的时间复杂性（仅用于自我练习）。解决方案之一是：

def is_hopable(arr):
    if len(arr) < 1 or arr[0] == 0:
        return False
    if arr[0] >= len(arr):
        return True
    res = False
    for i in range(1,arr[0]+1):
        res = res or is_hopable(arr[i:]) # This line  
    return res

我知道递归时间复杂度计算的一般想法，但我在分析注释行（在 for 循环内）时遇到了麻烦。通常我用 T（n） = C T（那条线）计算时间复杂度，并用一般表达式（例如 T（n-k））降低它，直到我达到基本情况并且可以用 n 表示 k，但是 for 循环的时间复杂度是多少？

Answer 1

循环的复杂度可能高达O（n^2），因为循环的每次迭代（最多n次迭代）都会执行一个切片arr[i：]，该切片返回arr的副本，而没有第一个i元素O（n）。考虑到这一点，总时间是O（n^3）。

提到的上限是紧的。< br >示例:< code>arr = [n-1，n-2，n-3，...，1，1]
替代形式:< code>arr[i] = n - 1 - i对于所有< code>i，< code>0

由于T(n)下界是3次多项式，我们发现问题运行时间的这种情况是ω(n^3)证明问题(O(n^3))的上界是紧的。

旁注：
如果您使用原始数组和当前索引作为参数，循环的运行时将为O（n），总时间O（n^2）。