请求协助计算一段C语言代码的时间复杂度

先看你给出的代码：

int funn(int n) {
    int i, j, k = 0;
    for (i = n / 2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n / 2;
    return k;
}

我们可以分两层循环拆解分析：

1. 外层循环的执行次数 #

外层循环起始值为n/2，终止条件是i <= n，每次i++。执行次数计算为：
n - n/2 + 1 = n/2 + 1
当n足够大时，常数项1和系数1/2可以忽略，因此外层循环的时间复杂度为O(n)。

2. 内层循环的执行次数 #

内层循环起始值为2，每次j = j * 2，直到j > n停止。这是典型的指数增长循环，推导次数如下：
假设执行k次，第k次循环后j的值为2^k，终止条件是2^k > n，即k > log₂n。因此内层循环的执行次数为log₂n，时间复杂度为O(log n)。

3. 总时间复杂度 #

嵌套循环的总执行次数是外层次数乘以内层次数，即(n/2 + 1) * log₂n。忽略常数项和系数后，总时间复杂度为O(n log n)。

你之前误以为是O(n)，应该是没注意到内层循环不是固定次数——它的执行次数和n的对数相关，不是常数。

给新手的几个分析小技巧：

• 嵌套循环的时间复杂度通常是各层循环复杂度的乘积（除非内层循环的终止条件和外层变量相关，这里内层只和n有关，所以直接相乘）
• 遇到每次乘/除固定数的循环，优先考虑对数级复杂度O(log n)
• 大O表示法只关注量级，可直接忽略常数、低阶项，比如n/2直接看成n，log₂n和log₁₀n在大O里等价，统一写成log n

内容的提问来源于stack exchange，提问作者sLang