o(n)的算法复杂度

Question

我最近开始玩这个普林斯顿课程的算法,我观察了以下模式

上)

 double max = a[0];
  for (int i = 1; i < N; i++)
     if (a[i] > max) max = a[i];

O(N ^ 2)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        if (a[i] + a[j] == 0)
           cnt++;

O(N ^ 3)

for (int i = 0; i < N; i++)
     for (int j = i+1; j < N; j++)
        for (int k = j+1; k < N; k++)
           if (a[i] + a[j] + a[k] == 0)
cnt++;

这里的常见模式是随着循环中的嵌套增长,指数也会增加.如果我有20-for循环,我的复杂性将是0(N ^ 20),这是安全的吗？

PS:请注意,20只是我选择的一个随机数,是的,如果你在代码中嵌套20个for循环,那么你显然有些不对劲.

Answer 1

这取决于循环的作用.例如,如果我将第二个循环的结尾更改为只进行3次迭代,如下所示:

for (int i = 0; i < N; i++)
    for (int j = i; j < i+3; j++)
       if (a[i] + a[j] == 0)
          cnt++;

我们回到O(N)

关键是循环中的迭代次数是否与N有关,并且与N一样线性增加.

这是第二个循环进入N ^ 2的另一个例子:

for (int i = 0; i < N; i++)
    for (int j = i; j < N*N; j++)
       if (a[i] + a[j] == 0)
          cnt++;

这将是o(N ^ 3)