求解给定while循环代码的时间复杂度并给出推导解释

结论 #

给定代码的时间复杂度为 O(1)（常数时间复杂度）。

对应推导与解释 #

待分析的代码如下：

R = 40;
while(R>=10){
  x = x-1;
  R = R div 2;
}

分析过程如下：

• 时间复杂度的核心是衡量算法运行耗时随问题输入规模增长的变化趋势，观察这段代码的变量可以发现：循环控制变量R的初始值是硬编码的固定常量40，不存在随外部输入变化的规模参数。
• 逐次模拟循环执行过程可以直接统计总执行步数：
  1. 初始R=40，满足R>=10的循环条件，执行1次循环内操作，R通过整数除法更新为40 div 2 = 20
  2. R=20，满足循环条件，执行第2次循环内操作，R更新为20 div 2 = 10
  3. R=10，满足循环条件，执行第3次循环内操作，R更新为10 div 2 = 5
  4. 此时R=5，不满足R>=10的条件，循环直接终止
• 整个流程中循环固定执行3次，循环内的两条语句都是单次原子操作，总执行步数是完全固定的常数，不会出现随输入规模增长耗时上升的情况，因此属于常数时间复杂度。

补充说明：如果修改代码逻辑，将R的初始值作为可变输入参数n传入，那么循环执行次数约为log₂(n/10)，对应时间复杂度为O(log n)，但该结论不适用于给出的R初始值固定为40的代码。

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