c - 什么时候是系列1 + 1/2 + 1/3 + 1/4 +…+ 1/n = log n的总和，什么时候是等于n的同一总和，即1 + 1/2 + 1/3 + 1/4 +…+ 1/n = n

在尝试查找大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)

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

最佳答案

对于前者，内部循环大约运行（正是n为2的幂）

n + n/2 + n/4 + n/8 + ... + n/2^log2(n)

次。可以分解成

n * (1 + 1/2 + 1/4 + 1/8 + ...  + (1/2)^(log2 n))

第二个因子称为the geometric series的（部分和）收敛，这意味着当我们接近无穷大时，它将接近一个常数。因此它是θ(1);当您将其乘以n时，您得到θ(n)



前几天我做了一个analysis of the latter algorithm。该算法中n的迭代次数为

ceil(n) + ceil(n / 2) + ceil(n/3) + ... + ceil(n/n)

它非常接近a partial sum the harmonic series乘以n：

n * (1 + 1/2 + 1/3 + 1/4 + ... 1/n)

与几何级数不同，谐波级数不会收敛，但是随着我们增加更多项，它会发散。第一个n项的部分和可以由ln n + C上下限制，因此整个算法的时间复杂度为θ(n log n)。

关于c - 什么时候是系列1 + 1/2 + 1/3 + 1/4 +…+ 1/n = log n的总和，什么时候是等于n的同一总和，即1 + 1/2 + 1/3 + 1/4 +…+ 1/n = n，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59713574/