nested - j+=sqrt(i) 时的时间复杂度

Question

我需要找到这个函数的时间复杂度(以 theta 为单位):

int x = 0; 
for (int i=1; i < n ; i++) { 
  for (double j=i; j <= n ; j+=sqrt(i)) { 
    ++x; 
  } 
}

我知道外循环进行 n-1 次迭代，内循环进行 (n-i)/sqrt(i) 次迭代，所以我需要计算 (n-i)/sqrt(i) 的 i=1 到 n-1 的 sigma )。知道如何做到这一点吗？

编辑:假设 sqrt() 的运行时间为 O(1)。

Answer 1

我不知道 sigma 和 theta 是什么意思，但是 sqrt 是一个常数时间运算，所以它在大 O 表示法中基本上无关紧要，即 j+=sqrt(i);与j+=i相同；与 j+=1; 相同。另外，(n-k) ~= n，因为 k 远小于 n。这意味着当 n 变大时，n-i 就变成了 n。所以 (n-i) * sqrt() = n * 1 = n。你对外循环执行了 n 次，所以 n^2。

添加:至于你的复杂系列，我确信这是准确的，但这不是我们关心的，我们关心的是操作的顺序。所以我们需要证明你的级数是 O(n^2) 或 K*n^2。所以你有 i + 2*i + ... (n-1)*i + n*i。其中 i 是常数，因此我们可以将其分解出来并将其包装在 K 中，剩下 1 + ... + n。该陈述以 n 为主，即当 n 变大时 n ~= (n-1)，并且 (n-1) ~= (n-2) 这意味着 (n-2) ~= n。现在，当我们接近零时，这不再成立，但是 n 太大了，我们可以删除前一百万项。所以我们留下了一些看起来像这样的函数C*(n-k)*n + c。其中 C、k 和 c 均为常数。由于我们不关心常数，我们只关心随着 n 的增长而增长，因此我们可以删除所有这些常数并只保存 n^2。或者，您可以证明您的级数以 n^k*n 为界，其中当 n 接近无穷大时 k 变为 1，但良好的逻辑论证通常会更好。 〜本