For循环的大O是什么,迭代平方根时代？

Question

我试图找到这个代码片段的大O:

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

由于循环运行√n次,我假设这个for循环是O(√n).但是,我在网上读到√n= O(logn).

这对于循环O(√n)还是O(logn)？

谢谢!

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.)