c++ - 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++) { ... }