请教Python某函数时间复杂度为何是O(√n)

把这个函数的循环过程拆成两个核心阶段分析就清晰了：

1. jump翻倍阶段 #

初始jump=1，只要jump² < n，jump就会每次乘2，直到jump ≥ √n才停止翻倍。
这个阶段的循环次数是log₂(√n)，也就是(1/2)log₂n，属于**O(logn)**量级，增长极慢，对整体复杂度几乎没有主导作用。

2. 固定jump累加阶段 #

当jump达到≥√n后，就不再变化了，之后每次循环都执行cur += jump，直到cur ≥ n。
此时每次累加的步长是√n左右，要让cur从当前值到n，需要的循环次数约为n / √n = √n次，这部分是**O(√n)**量级，是复杂度的主导项。

总结 #

两个阶段的总循环次数是O(logn) + O(√n)，由于√n的增长速度远快于logn，所以整体时间复杂度由主导项决定，即O(√n)。

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