算法的渐近复杂度（Big - O）

Question

我有以下示例：

i=2;
while i<=n {
   O(1)
   j=2*i
   while j<=n {
       O(1)
       j=j+i
   }
   i=i+1

我是计算渐近复杂度的初学者。我认为它是 O((n-1)*(n/4)) 但我不确定这个答案是否正确或者我遗漏了一些东西。

Answer 1

在内循环中，j 以 i 步从 2i 到 n，因此内循环运行 (n-2i)/i+1 次，即 n/i-1（整数除法）。

然后外层循环从 2 到 n 运行 i，总共 n/2-1+n/3- 1+n/4-1+...n/(n/2)-1 次内部迭代（对于较大的 i，没有迭代）。

该数量很难估计，但其边界为 n (H(n/2)-1)-n/2，其中 H 表示谐波数。

我们知道Hn~O(log n)，因此，渐进地，运行时间为O(n log n)。