单循环C语言函数的时间复杂度计算及推导方法咨询

该C语言函数的时间复杂度为O(√n)，不是O(logn)。

推导思路 #

先给出函数代码方便对照：

void f(int n){
    int i=1;
    int j=1;
    while(j <= n){
        i += 1;
        j += i;
    }
}

我们直接看循环内变量的变化规律：
初始状态i=1、j=1，每执行一次循环，i自增1，j累加最新的i值。假设循环总共执行了k次才终止，我们可以得到k次循环后j的取值为等差数列求和结果：

j = 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2

循环终止的条件是j > n，代入上面的求和公式可得近似关系：

k²/2 ≈ n

忽略常数系数后可得k ≈ √n，即循环执行次数的量级和√n成正比，因此时间复杂度为O(√n)。

小数值测试容易混淆的原因 #

n较小时√n和log₂n的数值非常接近：

• n=16时，√16=4，log₂16=4
• n=64时，√64=8，log₂64=8

但n增大后二者差距会快速拉开，比如n=256时，√256=16，log₂256=8，代入函数测试可得到循环执行次数为21次，和√n的量级完全吻合，和logn差距明显。

内容的提问来源于stack exchange，提问作者Achraf Ben Soltane