为何int algorithm(int n)函数的时间复杂度为O(log n)？

嘿，这个问题其实很好理解，咱们一步步拆解来看：

首先先把你给出的函数代码贴出来方便参考：

int algorithm(int n) {
    int k = 0;
    while(n>1) {
        n=n/2; // integer division
        k++;
    }
    return k;
}

这个函数的核心耗时部分就是那个while循环，循环执行的次数直接决定了它的时间复杂度。我们来用几个具体例子看看循环次数和输入n的关系：

• 当n=8时：循环执行3次（8→4→2→1，到1时停止），而log₂8=3，刚好对应；
• 当n=16时：循环执行4次，log₂16=4，完美匹配；
• 就算n不是2的整数次幂，比如n=7：循环执行2次（7→3→1），此时log₂7≈2.8，我们取它的渐近上界，依然是对数级别的量级。

本质上来说，每次循环都会把n通过整数除法减半——相当于每次都把问题的规模砍成原来的1/2。这种每次规模减半的操作，循环执行的次数必然是以2为底n的对数的量级。

而时间复杂度的O表示法描述的是输入规模n增大时，运行时间的增长趋势：这里n每翻一倍，循环次数只增加1次，完全符合对数级别的增长速度。在算法分析里，对数的底数不影响大O表示（因为不同底数的对数可以通过常数系数转换），所以我们统一写成O(log n)。

内容的提问来源于stack exchange，提问作者뚱프로그래머