sqrt时间复杂度比较

Question

这是循环吗--

for(int i = 0 ; i < sqrt(number) ; i++)
{
    //some operations
}

比这个快 --

int length = sqrt(number);
for(int i = 0 ; i < length ; i++)
{
    //some operations
}

我在在线法官的代码中得到了 TLE，但是当我用长度替换循环中的 sqrt 时，我接受了它。

你能否指出考虑到 number to be <=1000000000

的 sqrt 循环的时间复杂度

Answer 1

两个循环之间的时间复杂度本身没有区别（除非 sqrt 本身的复杂度取决于数量）但是是的不同之处在于很多时候你在计算平方根。

没有优化，比如编译器会自动将循环不变的东西移出循环（假设在这种情况下甚至允许这样做，因为编译器必须检查很多东西以确保它们不会影响结果或副作用sqrt 调用），以下代码将计算平方根大约一千次（每次迭代一次）：

number = 1000000;
for(int i = 0 ; i < sqrt(number) ; i++) { ... }

但是，这个代码只会计算一次：

number = 1000000;
root = sqrt(number);
for(int i = 0 ; i < root ; i++) { ... }

Answer 2

第一个版本强制编译器生成在每次测试条件时执行 sqrt(number) 的代码（与 for 循环次数一样多）。

第二个版本只计算一次长度（单次调用sqrt）。

Answer 3

问题是整个表达式 i < sqrt(number) 必须在原始代码中重复计算，而 sqrt 在修改后的代码中只计算一次。

嗯，最近的编译器通常能够优化循环，因此 sqrt 在循环之前只计算一次，但你想依赖它们吗？

sqrt time complexity comparison