算法分析大O表示法

Question

def function(n):
    if n <= 1:
       return
    function(n / 2)
    function(n / 2)

我只是想知道为什么这个函数有 O(n) 运行时间。

我看到每次调用这个函数时，它都会将输入的大小减少 2。所以我认为运行时会是 nlog(n) 因为它调用了该函数 2 次，所以它是 n 并且它调用它 self 但将输入减少 2，所以我认为这是另一个 logn。

谢谢大家的回答！！ 对于我的任何错误，我深表歉意。

Answer 1

分析如下。由于该函数在减半输入上调用自身两次，因此我们可以将运行时间写为

T(n) = 2 * T(n/2)

进一步扩展：

T(n) = 2 * T(n/2) = 4 * T(n/4) = ... = K * T(n/K) = n * T(1)

由于

K(1)

是

O(1)

，那么

n*K(1)

就是

O(n)

。 量子ED