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(n-k)）减少它，直到我达到基本情况并且可以用 n 表示 k，但是那个 for 循环的时间复杂度是多少？

Answer 1

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

提到的上限很紧。
示例：arr = [n-1, n-2, n-3, ..., 1, 1]
替代形式：arr[i] = n - 1 - i for all i, 0 <= i < n - 1, and arr[n-1] = 1 where n is length of arr.

递归计算基本运算量（避免使用常量）可以表示为：

简化求和：

评估（展开）T 的较小项并搜索下限：

使用 formula 从 1 到 n 的平方和：

由于 T(n) 下界是 3 次多项式，我们发现问题的此类实例运行时间是 Ω(n^3) 证明问题的上界 (O(n^3)) 很紧。

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

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

Python - How to calculate this recursive function time complexity?

big-o

time-complexity