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(that line)通常我用通用表达式（例如 T(nk)）计算时间复杂度并减少它，直到达到基本情况并可以用 n 表示 k，但是 for 循环的时间复杂度是多少？

Answer 1

该循环的复杂性for可能高达 ，O(n^2)因为循环的每次迭代（最多 n 次迭代）都会执行一个切片，该切片返回没有第一个元素arr[i:]的副本。考虑到这一点，总时间是。arriO(n)O(n^3)提到的上限是严格的。示例：arr = [n-1, n-2, n-3, ..., 1, 1]替代形式：arr[i] = n - 1 - i对于所有i, 0 <= i < n - 1，其中arr[n-1] = 1是n的长度arr。