如何统计包含平方根操作的算法的运算次数

我们先拆分你给出的代码的操作构成：

m = 0  // 1次固定操作
while(n>= 2)
  n = sqrt(n)
  m++
return m++ // 1次固定操作

一、固定开销操作 #

这部分操作和输入n的取值无关，一共2次：

• 初始化m = 0
• 最终return m++

二、循环相关操作 #

循环的逻辑是每次对n开平方，直到n小于2时终止。我们先计算循环体的执行次数k：
每次循环后n的值变为原来的平方根，即执行k次循环后，n的取值为 n^(1/2^k)，循环终止条件为 n^(1/2^k) < 2。
对终止条件两边连续取两次以2为底的对数，可得：
2^k > log₂(n) → k > log₂(log₂(n))
即循环体执行次数k为满足上述不等式的最小正整数，当输入n初始就小于2时，k=0。
循环内的操作统计：

• 每次进入循环前需要执行1次n≥2的判断，最终退出循环前还要执行1次判断，总判断次数为 k + 1
• 每次循环体内包含2次操作：n = sqrt(n)、m++，k次循环总操作数为 2k
  所以循环部分总操作数为 (k+1) + 2k = 3k + 1

三、总操作数计算 #

边界情况（初始n < 2） #

循环体执行0次，总操作数 = 2次固定操作 + 1次循环判断操作 = 3次

常规情况（初始n ≥ 2） #

总操作数 = 2次固定操作 + 3k +1次循环操作 = 3k + 3，其中k = ⌈log₂(log₂n) + 1⌉
举个实例验证：n=16时，log₂(log₂16)=2，k=3，总操作数=3*3+3=12次，逐行计数和计算结果一致。

四、时间复杂度结论 #

该算法的时间复杂度为 O(log log n)，属于增长非常缓慢的复杂度等级。 #

内容的提问来源于stack exchange，提问作者Talon Tài