c - 1+1/2+1/3+1/4+......+1/n=log n 的和何时等于 n，即 1+1/2+ 1/3+1/4+……+1/n=n

Question

我对渐近分析很陌生，在尝试找到大 O 表示法时，在一些问题中，对于级数的相同简化，它被给出为 log n ，而对于另一个问题，它被给出为 n 。

问题如下:

int fun(int n)
{
    int count = 0;
    for (int i= n; i> 0; i/=2)
        for (int j = 0; j < i; j++)
            count ++;
    return count;
} 

T(n)=O(n)

int fun2(int n)
{
    int count = 0;
    for(i = 1; i < n; i++)
        for(j = 1; j <= n; j += i)
            count ++;
    return count;
}

T(n)=O(n log n)   

我真的很困惑。为什么这些看似相似的算法复杂度却不同？

Answer 1

两种情况形成的系列是不同的时间复杂度分析

1. 在这种情况下，第一个 i 将是 n，j 的循环将持续到 n >，那么i将是n/2并且循环将一直进行到n/2等等，所以时间复杂度将是

    = n + n/2 + n/4 + n/8.......
   

   这个和的结果是 2n-1因此时间复杂度为 O(n)

2. 在这种情况下，当i为n时，我们将循环j n次，下次i 将是 2，我们将一次跳过一个条目，这意味着我们将迭代 n/2 次，依此类推。所以时间复杂度为

    = n + n/2 + n/3 + n/4........
    = n (1 + 1/2 + 1/3 + 1/4 +....)
    = O(nlogn)
   

   1 + 1/2 + 1/3... 的总和为 O(logn)。如需解决方案see .