求下述算法的大Θ符号时间复杂度，能否得到更紧约束？

先直接给结论：这段代码的时间复杂度是Θ(n)，比你提到的O(nlogn)更紧。

分析过程： #

外层循环从i=1到i=n-1，共执行n-1次。核心是统计每个i对应的内层while循环的执行次数——这个次数其实就是i中包含的2的因子个数（比如i=8=2³，循环执行3次；i=6=2×3，循环执行1次）。

总执行次数等于所有i∈[1,n-1]的2的因子个数之和，我们可以按2的幂次拆分统计：

• 能被2整除的数（偶数）：共有⌊(n-1)/2⌋个，每个至少贡献1次循环；
• 能被4整除的数：共有⌊(n-1)/4⌋个，每个额外多贡献1次循环；
• 能被8整除的数：共有⌊(n-1)/8⌋个，再额外多贡献1次循环；
• ……
• 直到2的幂次超过n-1，后续项为0，停止统计。

把这些项加起来，总次数S = ⌊(n-1)/2⌋ + ⌊(n-1)/4⌋ + ⌊(n-1)/8⌋ + ...

上界推导：

把每个⌊x⌋替换为x，得到：
S ≤ (n-1)/2 + (n-1)/4 + (n-1)/8 + ...
这是首项为(n-1)/2、公比为1/2的等比数列求和，结果为n-1，即S = O(n)。

下界推导：

当n足够大时，⌊(n-1)/2^k⌋ ≥ (n-1)/2^k - 1，代入求和：
S ≥ [(n-1)/2 -1] + [(n-1)/4 -1] + ... + [(n-1)/2^m -1]
其中2^m ≤ n-1 < 2^(m+1)，m是log2(n-1)的整数部分。
展开后：
S ≥ (n-1)(1/2 + 1/4 + ... + 1/2^m) - m
等比数列和1/2 + ... +1/2^m = 1 - 1/2^m ≥ 1 - 1/(n-1)，代入得：
S ≥ (n-1)(1 - 1/(n-1)) - log2(n) = n-2 - log2(n)
这显然是Ω(n)的。

因为总次数S既是O(n)又是Ω(n)，所以S = Θ(n)，整个算法的时间复杂度就是Θ(n)。

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