代码增长的算法顺序

Question

我正在网上上课并坚持以下问题.以下代码片段的最坏情况运行时间的增长顺序是N的函数是多少？

int sum = 0;
for (int i = 1; i <= N*N; i++)
    for (int j = 1; j <= i; j++)
        for (int k = 1; k <= j; k++)
            sum++;

我认为这是顺序,N^4但似乎这个答案是错误的.你能解释一下吗？

Answer 1

它是有序的O(N^6).您应该注意,每个循环都只是简单N地为复杂性添加顺序.考虑以下示例:

int sum = 0;
for (int i = 1; i <= M; i++)
    for (int j = 1; j <= i; j++)
        for (int k = 1; k <= j; k++)
            sum++;

您应该能够O(M^3)轻松地确定它是有序的,所以如果您更换M=N^2,那么您将得到答案.关键是O(N^2)在这种情况下每个内循环都是有序的,但不是O(N).

Answer 2

内循环的一次运行会sum精确地增加j一次。

中间循环的一次运行精确地调用内部循环i，其值在和j之间（包含）。因此它会精确地增加倍，这是由著名的“三角数”公式得出的。1isum1+2+3+...ii.(i+1)/2

外层循环精确调用中间循环N^2几次（让我们将其表示为M），其值i在1和 之间M（包含）。所以它sum精确地增加了1+3+6+...M.(M+1)/2倍。同样，这是M.(M+1).(M+2)/6由不太知名的“四面体数”公式（http://en.wikipedia.org/wiki/Tetrahedral_number）得出的。

总而言之，最终的sum值为N^2.(N^2+1).(N^2+2)/6。

用渐近术语思考，内循环是O(j)，中间循环O(i^2)（通过求和）和外循环O(M^3)（通过求和），即O(N^6)。

另请参阅 Faulhaber 公式，该公式显示 的总和n^k为O(N^(k+1))( http://en.wikipedia.org/wiki/Faulhaber%27s_formula )。