algorithm - 用算法计算最坏情况的时间复杂度

Question

这是我的学习指南上的一个问题，但我不确定如何开始这个问题，甚至不确定代码“to n do”的含义。我已经看到其他一些问题得到解答，这些问题也在寻找最坏情况下的时间复杂度，但没有与此问题类似的代码。我只是在寻找解决这些问题的通用方法，所以如果有 go to 方法，我真的很想得到一些帮助。问题如下。

Compute the worst case time complexity of the following algorithm.

for i = 1 to n do
    for j = 1 to i do
        for k = 1 to j do
            print(i,j,k).

Answer 1

在我看来，在这种情况下没有最好或最坏情况的时间复杂度，只有时间复杂度。如 this 中所述维基百科文章，最好和最坏的情况通常适用于排序函数等函数，其中算法花费的时间将取决于输入的初始排序方式。因此，在您的情况下，按照下面的 matlab 代码的结果，我会说时间复杂度是

1/6*n*(n+1)*(n+2)

这是通过针对不同的 n 值运行代码而得出的，并注意 n 的每个增量都会添加相应的打印语句三角形数，即

sum_{i = 1}^{n} 1/2*i*(i+1) = 1/6*n*(n+1)*(n+2)

Matlab代码:

n = 5;

count = 0;
for i = 1:n
    for j = 1:i
        for k = 1:j
            count = count + 1;
        end
    end
end

1/6*n*(n+1)*(n+2)
count