performance - 嵌套循环的大 O 运行时间？

Question

如何计算此代码的大 O 运行时效率？我的直觉告诉我它是 O(n^3)，但我不确定，因为我不确定循环是独立的还是相关的。

for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
        for (k=1; k<=n; k++)
          print ("%d %d %d/n", i, j, k);

Answer 1

你的直觉是对的。您有三个嵌套的 for 循环遍历 n，因此对于前 n 个循环中的每一个，您都创建了另一个 n 个循环，每个循环又创建了 n 个循环。因此 O(n^3)。

编辑:想想这将如何进行-i 首先是 1，j 也是 1，然后 k 循环 1 到 n。只有在k经历了整个循环之后，j才会增加到2，然后k再次经历循环，依此类推。