渐近分析

Question

我不太明白如何将这个转化为公式。

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j += i) {

我理解的是，每次 i++ 都会使 j 的乘法层数减少1。

当 i = 1 时，j 取值范围为 1, 2, 3, ..., 100。 当 i = 2 时，j 取值范围为 1, 3, 5, ..., 100。

我不确定如何用大O符号来表示这个关系。

j 的总和可以表示为 N, N/2, N/3, N/4..., N/N （我的结论）。

如何将其表示为 N 的函数呢？

- Mappan

---

你的问题实际上可以简化为，“调和级数1/1 + 1/2 + 1/3 + ... + 1/N的紧密界限是什么？” 答案是 log N（你可以把它看作连续求和而不是离散求和，注意到 1/N 的积分是 log N）。 - justhalf

第二个循环基本上是这样。但总体而言，在大O符号方面，如何最好地思考这段代码呢？也就是说：我猜第一个循环是N，第二个循环是调和级数，但我一直在做这些问题来掌握这个技巧，我的数学似乎总是让我失望。 - Mappan

你似乎误解了一些事情。调和级数（好的，乘以N）_是_整个算法的大O符号。请注意，对于没有第一个循环的第二个循环，大O符号将固定为N/i。 - justhalf

是的，你说得对。我注意到，正如你在下面指出的那样，1/N的积分=ln(N)。将这个公式与我的结果进行比较，得到了相当相似的线条。 - Mappan

Answer 1

因此，你的问题实际上可以简化为“调和级数1/1 + 1/2 + 1/3 + ... + 1/N的紧密界是什么？” 答案是$log N$（您可以将其视为连续总和而不是离散总和，并注意$1 / N$的积分是$log N$）。

你的调和级数本身就是整个算法的公式（正如你正确地得出结论的那样）。

所以，���的总和：

N + N/2 + N/3 + ... + N/N = N * (1 + 1/2 + 1/3 + ... + 1/N) = Theta(N * log N)

因此，该算法的紧密界限为N * log N

在此处查看[严格的]数学证明（请参见“积分测试”和“发散率”部分）

- justhalf

---

我以前从未见过这个。有趣。 - Giovanni Botta

Answer 2

好的，您可以系统地使用Sigma符号：

- Mohamed Ennahdi El Idrissi