algorithm - 代码片段的运行时间是多少

Question

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

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

Answer 1

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

while (i <= n);

在while 循环 语句后有一个分号表示循环语句下面没有语句。供您引用，此 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) .