以下循环的时间复杂度应该是多少？

Question

请检查下面的时间复杂度是否正确。

循环 1

for(int i =0; i*i < n; i+=2)

我认为在这个循环中完成的工作将是 O(sqrt(n)) 因为我知道条件会当我到达 sqrt(n) 时被满足。此外，增量器 (i +=2) 将导致结果在 n/2 内完成，因此完成的总体工作将为 sqrt(n)/2.

循环 2

for(int i =0; i*i < n; i*=2)

我认为在此循环中完成的工作将是 O(log(n)) 因为与上一个问题唯一不同的是增量器 (i*=2 ) 这将导致循环 运行 in log(n) 次。所以整体工作变成 log(sqrt(n)) 变成 O(log(n))

PS：如果有人有关于各种循环变体或嵌套循环的时间复杂度的秘籍sheet，请分享。非常感谢您的帮助。

Answer 1

在第一种情况下，你的假设是正确的。时间复杂度为 O(sqrt(n))。我们在计算时间复杂度时不考虑增量器 +=2，因为我们只采用最大幅度的修改器，在这种情况下 i*i < n.

在第二种情况下，你是对的。但是，请注意循环从 i=0 开始，并且由于此变量的增量是通过 i*=2 完成的，因此它将永远保持值 0，因为 0*2 = 0.