含嵌套if语句的while循环代码Big-O时间复杂度判定

你的判断中，第一段代码的时间复杂度结论正确，第二段代码的时间复杂度结论有误，正确结果如下：

• 第一段代码：O(n)
• 第二段代码：O(√n)

我们可以通过循环变量的变化趋势判断循环次数：
循环的终止条件是a >= b，初始状态下a=0、b=n，两者的差值为n。
每次进入循环，不管走哪一个分支：

• 进入乘积等于n的分支：a+1、b-1，两者差值减少2
• 进入乘积大于n的分支：b-1，两者差值减少1
• 进入乘积小于n的分支：a+1，两者差值减少1

也就是说每次循环，a和b的差值至少减少1，因此循环最多执行n次就会终止。每次循环内的所有操作都是O(1)的常数操作，因此整体时间复杂度为O(n)，和你的判断一致。
乘积等于n的分支的执行次数不影响整体复杂度，因为不管是否进入该分支，单次循环的开销都是常数级。

你误认为它是O(log n)，大概率是看到了b = n/a这步操作的压缩效果，但实际上这个代码的最坏时间复杂度是O(√n)，原因如下：
我们可以观察循环的终止边界：当a > √n时，如果还满足b > a，那么a*b > a*a > n，此时会触发b = n/a的操作，而n/a < √n，执行后b就会小于a，循环直接终止。
也就是说a的取值上限最多到√n，而在最坏场景下（比如n为质数），除了第一次循环外，后续大部分循环都会走a++的分支，a会从1开始逐次增长到√n，此时循环的总次数就是O(√n)级，远高于O(log n)的增长速度。
b = n/a的操作确实会减少b的取值，但不会改变a最多增长到√n的上限，因此整体时间复杂度为O(√n)。

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