algorithm - 计算 FOR 循环标记如何影响复杂性

Question

假设我们有一个 FOR 循环

int n;

for (int i = 0; i < sqrt(n); i++)
{
    statement;
}

计算 i 的 sqrt 是否会增加循环的 O(n) 复杂度？在我的示例中，Java 中的 sqrt 函数的时间复杂度为 O(log n)，这对循环的时间复杂度有何影响？ sqrt 函数是应用于循环的每个序列还是仅应用一次并且该值被存储并再次使用？

Answer 1

我想这可能取决于语言，但通常i < sqrt(n)检查将在每个循环迭代后运行，因此有效，您可以将其称为 sqrt(n)次。好主意是存储 sqrt(n)结果变量并将其与 i 进行比较，所以

int n;
double sn = sqrt(n);

for (int i = 0; i < sn; i++)
{
    statement;
}