作业：如何计算这个函数的时间复杂度？

Question

void func(int n){
    int i=1, k=n;
    while (i<=k){
        k=k/2;
        i = i*2;
    }
}

如何计算这个函数的时间复杂度？我知道 i=1, k=n 的赋值需要两个基本步骤，除以 k 的值并乘以 i 的值也需要两个基本步骤，但是因为 i 和 k 的值呈指数增加和减少, 时间复杂度是 O(log base 4 N) 还是 O(log base 2 sqrt(N))?

Answer 1

你的答案是 O(log √n)，@Eraklon 在评论中说它是 O((log₂ n)/2)，@matri70boss 说它是 O( log₄n）。你们三个都是正确的，但最简单形式的答案是 O(log n)。

• log √n = log n^0.5 = 0.5 log n，我们在写大O的时候舍弃常数因子0.5。
• (log₂ n)/2 = (log n)/(2 log 2) 由 change of base identity 和 1/(2 log 2) 是另一个我们可以丢弃的常数。
• 同样，log₄ n = (log n)/(log 4)，我们可以舍弃常数因子 1/(log 4)。