12

我在 StackOverflow 上进行了一些搜索，并了解了 j-loop 的复杂性，即. 然而，随着 k 循环的嵌套添加，我很困惑为什么复杂性变成. 有人可以帮我理解这一点吗？O(n2)O(n3)

据我了解，i-loop 有 n 次迭代，而 j-loop 有 1+2+3+...+n 次迭代n*(n+1)/2，即.O(n2)

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

编辑：感谢您的所有帮助:) Balthazar，我已经编写了一段代码，它将根据计数器所在的循环递增计数器，这是一种粗略的逐步方式：

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

我以 1 为增量从 n=2 到 n=9 运行此代码，并得到以下序列：

因此，从计数器可以看出： i = n-1 给出了 O(n) 的复杂度，而 j = ((n-1)*n)/2 给出了复杂度。K 的模式很难发现，但已知 K 取决于 J，因此：O(n2)

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6给出一个复杂度O(n3)

我希望这对未来的人们有所帮助。

EDIT2：感谢Dukeling的格式 :) 在最后一行也发现了一个错误，现在更正

4

5 回答 5

16

如果您习惯使用 Sigma 表示法，这里有一个正式的方法来推断您的算法的时间复杂度（精确的普通嵌套循环）：

在此处输入图像描述

注意：公式简化可能包含错误。如果您发现任何东西，请告诉我。

于 2014-03-15T01:01:10.553 回答
7

k-loop 的复杂度为 O(ji)

j-loop 的复杂度为 O((ni)*(ni))

i-loop 的复杂度为 O(n*n*n)=O(n^3)

无论如何，你知道它不是 O(n^2) 因为前两个循环是 O(n^2) 并且它不超过 O(n^3) 因为只有 3 个循环

于 2013-08-28T11:31:47.337 回答
2

看一下这个例子来评估最坏情况的复杂性。

本质上，如果您逐行评估它，您将得到类似 O(n^3 / C) 的结果，其中 C 是某个常数，通常在此类评估中被跳过，导致 O(n^3)。

于 2013-08-28T11:31:16.533 回答
1

首先，我们将考虑内部循环的迭代次数与外部循环索引的值无关的循环。例如：

for (i = 0; i < N; i++) {
      for (j = 0; j < M; j++) {
             sequence of statements
      }
  }

外循环执行 N 次。每次外循环执行，内循环执行M次。结果，内循环中的语句总共执行了 N * M 次。
因此，两个循环的总复杂度为 O(N2)。
同样，三个循环的复杂度是 O(N3)

于 2014-04-29T10:19:02.360 回答
1

这在没有图表的情况下很难解释，但是每个嵌套循环都会在将迭代返回给父级之前迭代“n”次。

正如 jambono 指出的那样，每个嵌套循环都需要对“n”的每次迭代进行比较/评估。因此，“n”与每个循环中的局部变量 (n*n*n) 进行比较，结果为 O(n^3)。

在调试器中单步执行代码，以直观地指示机器如何处理这种复杂性。

于 2013-08-28T11:41:08.120 回答