家庭作业：如何计算此函数的时间复杂度？

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= logn ^0.5 = 0.5 logn，当我们使用大O表示法书写时，我们将常数因子0.5丢弃。
• [log ₂ n）/ 2 = [logn] /（2log2），[1 / log2]是我们可以舍弃的另一个常数。
• 同样，log ₄ n =（logn）/（log4），我们可以舍弃常数因子1 /（log4）。