这个算法的复杂性？

Question

如果 func2 = O(n) 且 func3 = O(n^2)，func1 的复杂度是多少？

void func1 (int n) {
    int i, j, k;
    for (k=0;k<n;k++)          // O(n)
        printf("%d",k);
    i=0;
    while (i<2*n) {         // O(n)
        for (j=i;j>1;j--)   // Not executed
            for (k=15;k>0;k--)
                func2(n);
        for (j=n;j>1;j--)  // O(n)
            func3(n);      // O(n^2)
        i++;
    }
}

所以这是 O(n^2)O(n)O(n) + O(n) = max(O(n^4),O(n)) = O(n^4) ?

谢谢！

Answer 1

void func1 (int n) {
  int i, j, k;
  for (k=0;k<n;k++)       
      printf("%d",k);
  i=0;
  while (i<2*n) {             // O(2*n) = O(n)
    for (j=i;j>1;j--)           // O(n)
        for (k=15;k>0;k--)        // O(15) = O(1)
            func2(n);               // O(n)
    for (j=n;j>1;j--)           // O(n) 
        func3(n);                 // O(n^2)
    i++;
  }
}

对于序列，找到步长的最大值。

根据经验，嵌套循环会成倍增加，但如果它们不是独立的，您可能需要仔细检查范围以确保情况确实如此（有关示例，请参见 Paul 的评论）。

这个算法的复杂性？

Complexity of this algorithm?

algorithm

big-o

time-complexity