recursion - 下面算法时间复杂度的解释

Question

我有以下算法：

def func(n):
    if n <= 1:
        return 1
    x = 0
    for i in range(n ** 2):
        if i % 4  == 0:
            x += i
    return x + func(n//3) + func(n//3) + func(n//3)

复杂度分析为：

$ T(n) = n^2 + 3*T(\frac {n}{3}) + 1 $

我知道复杂性是 $ O(n^2) $，但我的问题是，如果没有递归调用，那么复杂性怎么可能相同？对此有什么直观的解释吗？

标签： recursiontime-complexity

Answer 1

算法复杂度是最昂贵操作的时间/空间。如果其他操作与它相比成本更低，它们不会影响算法的复杂性。

例如，如果算法在T(n) = n^2 + log(n)-> O(n)=n^2since中运行，log(n)则不会影响，因为随着变量的增加n^2，它比它低得多。n

即使T(n) = n^2 + 3n^2 = 4n^2->O(n)=n^2因为标量4不会将复杂性提升到另一个量化级别，因为变量 n（最重要和最昂贵的部分）的依赖关系是相等的。