algorithm - 使用 log n 递归大 o

Question

这个函数的大 O 是什么：

def foo(n):
    if (n <= 1):
        return 0
    else:
        return n + foo(n/2) + foo(n/2)

我认为它可能是 O(2^logn) 因为在每个调用中，还有另外两个调用，并且 n 除以 2 直到它达到 1，因此是 logn。

标签： algorithmperformance

Answer 1

是的，它是O(2 ^logn )，它实际上等同于O(n)。

你可以分析如下：

T(n) = 1 + 2T(n/2)
        = 1 + 2(1 + 2T(n/4)) = (2²-1) + 2²T(n/4)
        = (2²-1) + 2²(1 + 2T(n/8)) = (2³-1) + 2³T(n/8)
        ...
        = (2 ^logn - 1) + 2 ^logn
        = (n-1) + 2n
        = O(n)

这可能是一个令人惊讶的结果，但是一个测量n和调用次数之间的分数的片段foo说明了这种时间复杂度：

let counter;

function foo(n) {
    counter++;
    if (n <= 1)
        return 0;
    else
        return n + foo(n/2) + foo(n/2);
}

for (let n = 1; n < 100000; n*=2) {
    counter = 0;
    foo(n);
    console.log(counter/n);
}