代码段的运行时间是多少

Question

谁能帮我找出以下代码片段的运行时间复杂度？

请帮我找出上面给出的代码片段的运行时间复杂度。

Answer 1

我猜你的代码有问题，特别是在第一个 while 循环中。

while (i <= n);

在while loop语句后有一个分号表示循环语句下面没有语句。供您参考，此 while 循环将无限运行因为您没有更新循环变量 i.

如果你错误地输入了那个分号，那么 while 将迭代 n 次，这将使 while 循环的时间复杂度为 O(n).

但是第二个 while 循环的时间复杂度是 O(log n)，因为您通过将值减半来减少循环变量 j。

while (j > 0)
    y := x/(2*j);
    j = j /2; 
    i = 2 *i;

因此，如果同时考虑两个 while 循环，总时间复杂度应为 O(n + log n)，相当于 O(n).

What is the running time of the code snippet