algorithm - 这个程序的确切复杂度是多少？

Question

有人给我这段代码，我想找到确切的复杂度，或者换句话说，找到一个公式，让特定的 n 知道如何计算 L。

L = 0;
for (i = 1; i<n; i++)
    for (j = 1; j<i; j++)
        for (k = j; k<n; k++)
            L++;

我的第一个想法是 (n^3 + n^2)/2，但是错了。

例如 n=5 L=20 ; n=10 L=240

谢谢:D

编辑: 这个问题来自 Fundamentals of Algorithms, page 140 or slide 161 in pdf (this is a free book version) http://www.freebookspot.es/Comments.aspx?Element_ID=76025

Answer 1

首先:复杂性与 n 的具体数字无关。它是关于渐近行为的。当有人说算法的复杂度是 O(f(n)) 时，这并不意味着算法严格执行 f(n) 操作。事实上，它可以执行 2*f(n) 或 1/2 * f(n) 或 f(n) + sqrt(f(n) )。在谈论复杂性时，人们通常感兴趣的是操作数量随着输入的增长而增长的速度。

在您的情况下，您必须编写 3 个嵌套总和(每个循环一个)和内部操作的总和成本(假设为 1):

这是精确的公式(不要相信我 - 使用 wolfram|alpha 检查)，但在复杂性语言中它只是 O(n^3)

UPD:请注意，此公式对应于条件类型为 less-or-equal 而不仅仅是 less-than 的循环。