确定函数的渐近复杂度

Question

这是我的家庭作业问题。我不知道这样的问题是否违规。我无法弄清楚这一点。我希望能帮助您理解为什么答案是这样的。

我可以自信地说，在这种情况下，我们会关注 θ 作为渐近复杂性的最精确描述，因为循环永远不会提前终止。

我知道外部 for 循环将始终运行

次，而内部 for 循环将随着

的增加运行更少的次数。

答案就是 θ(n * 内循环的运行时间)。

我认为从 k=1 到 n(n+1)/2 的 Σ 或从 k = i 到 i/1 的 N 的调和级数 Σ 在这里可能有用，但我不知道如何应用任何一个。我们在课堂上回顾了相对简单的例子，我理解那些，但不理解这个。

void function(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j += i) {
            std::cout << "*";
        }
    }
}

制作一个表格，列出当 n 为某个值时 i 和 j 的理论值，并尝试找到 i 和 j 之间的数学关系。

例如：说 n = 3。

Answer 1

您的总复杂度是

(n / 1) + (n / 2) + ... + (n / n) =

n * ((1 / 1) + (1 / 2) + ... (1 / n)) =

n * (ln(n) + 0.577) 大约为 nlogn。

原因是

(1 / 1) + (1 / 2) + ... + (1 / n)