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

Question

假设我们有一个FOR循环

int n;

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

计算i的sqrt会增加循环的O(n)复杂度吗？在我的例子中，Java中的sqrt函数的时间复杂度为O(log )，这对循环的时间复杂度有什么影响？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;
}

Answer 2

sqrt函数应用于循环的每个序列。不过，n的用法有所不同。sqrt的O(logn)的复杂度是n是值中的位数，但是循环的O(n)是实际值n。有了n的定义，sqrt就更像O(loglogn)了。

对于这样的循环，像sqrt这样的数字操作的复杂性可以看作是恒定的时间。比特的数量是有限的，因此与更大的循环相比，时间是微不足道的。

Answer 3

对于问题中给出的变量n，

O(日志(d=bits of variable) * sqrt(n=number in the loop))

假设找到n位(位)数‘sqrt是log(D)，如'fgb’首先所说的。

假设n的位数在整个计算过程中对于所有硬件都是恒定的，所以：

O(log(常量)* sqrt (n))

O(常量* sqrt(n))

O(sqrt(n))

但是如果它不是强类型的，并且如果n的比特逐渐增加(例如从64比特到128到256比特到1024，但是具有相同的值)，那么它将是

O(log(d)*sqrt(n))