两类for循环的时间复杂度求解及数学证明咨询

一、两个循环的时间复杂度推导 #

循环1：for(int i=n;i>n/2;i=i/2) #

时间复杂度：O(1)
数学推导：
设循环执行k次，每次迭代后i的值为n/(2^k)。循环终止条件为i <= n/2，代入得不等式：
n/(2^k) <= n/2
两边除以正整数n（n>0），简化为：
1/(2^k) <= 1/2 → 2^k >= 2 → k >=1
但第一次迭代后，i变为n/2，此时i > n/2的条件不成立，循环直接终止。实际执行次数仅为1次，属于常数次数，因此时间复杂度为O(1)。

循环2：for(int i=n;i>0;i=i/2) #

时间复杂度：O(log n)
数学推导：
设循环执行k次，第k次迭代后i的值为n/(2^k)。循环终止条件为i <=0，由于n是正整数，我们需要找到最大的k，使得第k次迭代前i仍满足i>0：
第k次迭代前i的值为n/(2^{k-1})，需满足n/(2^{k-1}) >0，同时迭代后n/(2^k)会趋近于0，最终触发终止条件。整理得：
2^{k-1} <=n → k-1 <= log₂(n) → k <= log₂(n)+1
循环执行次数为floor(log₂(n)) +1，该次数与log n同阶，因此时间复杂度为O(log n)。

二、该类循环时间复杂度的通用证明方法 #

对于变量每次以常数倍数缩放（乘/除固定常数）的循环，可按以下步骤证明：

1. 明确循环三要素：记录变量初始值（如i=n）、迭代规则（如i=i/2）、终止条件（如i>0）。
2. 迭代表达式建模：写出第k次迭代后变量的数学表达式，比如每次除以常数c时，i = n/(c^k)；每次乘以常数c时，i = n*c^k。
3. 建立终止不等式：将迭代表达式代入终止条件，解出k的取值范围，得到循环执行的最大次数k_max。
4. 确定复杂度阶数：根据k_max的表达式匹配对应复杂度（常数次数为O(1)，与log n成正比为O(log n)，与n成正比为O(n)等）。

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