一个for循环迭代平方根次数的时间复杂度是什么？

Question

我正在尝试找出这段代码的时间复杂度（Big O）：

for (j = 0; j < Math.pow(n,0.5); j++ ) {
 /* some constant operations */
}

自循环运行次数为√n，因此我假设这个for循环的时间复杂度为O(√n)。然而，我在网上阅读到 √n = O(logn)。

所以，这个for循环的时间复杂度是O(√n)还是O(logn)？

谢谢！

- Jay

---

“√n = O(logn)”这种说法太荒谬了。你从哪里看到的？很明显，循环将运行“O(sqrt(n))”次。 - Niklas B.

你在哪里看到 √n = O(logn) 这个说法？当然，O(√n) != O(logn)，因为 √n != log(n)。也许原意是某种计算 √n 的算法的复杂度是 O(logn)。 - Ted Hopp

请提供证明 O(√n)=O(logn) 的链接。事实上，对于较大的 n，O(√n) > O(logn)。 - Matt

假设 n 在循环过程中没有变化 :) :) - ajb

@TedHopp：“O(√n) != O(logn) since √n != log(n)”现在这个论点和原始陈述一样错误... - Niklas B.

Answer 1

需要做出几个假设，但是这个循环的时间复杂度似乎为O(√n)。这些假设如下:

• 无论j的值为何，循环体都在恒定时间内执行。
• 在循环体内不会修改j的值
• 在循环体内不会修改n的值
• Math.pow(n,0.5)在恒定时间内执行 (可能为真，但取决于具体的Java执行环境)

正如一条评论所指出的那样，这也假设循环初始化是j=0而不是j-0。

请注意，如果重写循环，循环的效率将会更高：

double limit = Math.pow(n, 0.5);
for (j = 0; j < limit; j++ ) {
 /* some constant operations */
}

（仅当主体不更改 `n` 时，此为有效的重构。）

- Ted Hopp

---

如果n是一个局部变量，我希望它至少会进行优化，但也许我是错的。 - Niklas B.

@NiklasB。Java 不知道 Math.pow 会始终返回相同的值，即使参数相同（如果这是你想问的）。 - Sotirios Delimanolis

@NiklasB. - 这对编译器来说是一个很大的要求。它不仅需要能够确定 n 没有改变值（将其声明为 final 会有所帮助），而且编译器还需要知道每次使用相同参数调用 Math.pow(n,0.5) 时返回相同的值。我认为编译器没有整个标准 API 的如此详细的模型可用。 - Ted Hopp

如果循环语句中使用j * j < n而不是j < Math.pow(n, 0.5)，那么一切都会更好。让整数保持整数，浮点数保持浮点数。 - Dawood ibn Kareem

@David：在每次迭代中j * j < n会产生一个整数乘法；除了小的n，为一次性计算整数平方根更有优势（不幸的是没有作为此类的可用，必须通过浮点sqrt来模拟）。 - user1196549

Answer 2

假设对于某个函数P，pow操作的成本为O(P(n))，那么循环的全局成本为O(√n.P(n))。如果将pow调用从循环中分离出来，仅执行一次，则成本表达式为O(√n+P(n))。

如果P(n)=1，则它们分别为O(√n)和O(√n)。

如果P(n)=log(n)，则它们分别为O(√n.log(n))和O(√n)。

[总和的低阶项被其他项吸收。]

假设P(n)=log(n)，在任意精度整数的情况下可能是有效的，其中表示整数n至少需要O(log(n))位。但这只有在处理大值n时才有意义。

- user1196549