c++ - 通过计算步数计算算法复杂度

Question

尝试通过计算步数来计算函数的大 o。我认为这些是如何按照示例中的操作方式来计算每个步骤，但不确定如何计算总数。

int function (int n){
   int count = 0;                              // 1 step
   for (int i = 0; i <= n; i++)                // 1 + 1 + n * (2 steps)
      for (int j = 0; j < n; j++)              // 1 + 1 + n * (2 steps)
         for (int k = 0; k < n; k++)           // 1 + 1 + n * (2 steps)
            for (int m = 0; m <= n; m++)       // 1 + 1 + n * (2 steps)
               count++;                        // 1 step
  return count;                                // 1 step
}

我想说这个函数是 O(n^2)，但我不明白它是如何计算的。

我一直在看的例子

int func1 (int n){
       int sum = 0;                                // 1 step
       for (int i = 0; i <= n; i++)                // 1 + 1 + n * (2 steps)
          sum += i;                                // 1 step
       return sum;                                 // 1 step
}                                                  //total steps: 4 + 3n

和

int func2 (int n){
           int sum = 0;                                // 1 step
           for (int i = 0; i <= n; i++)                // 1 + 1 + n * (2 steps)
              for (int j = 0; j <= n; j++)             // 1 + 1 + n * (2 steps)
                  sum ++;                              // 1 step
           for (int k = 0; k <= n; k++)                // 1 + 1 + n * (2 steps)
               sum--;                                  // 1 step
           return sum;                                 // 1 step
    }      
                                                       //total steps: 3n^2 + 7n + 6

Answer 1

您刚才在此处提出的是非常简单的示例。 在我看来，您只需要了解循环中的复杂性是如何工作的，就可以理解您的示例。

简而言之(非常简短)必须在 asymptotic complexity 中考虑一个循环如下:

loop (condition) :
  // loop body
end loop

• 循环的条件应该告诉您循环将执行多少次与输入的大小相比。。<
• 主体的复杂性(您可以将主体视为子函数并计算复杂性)必须乘以循环的复杂性。

原因很直观:你在主体中的内容将被重复执行，直到条件得到验证，即循环(以及主体)将被执行的次数。

---

举个例子:

// Array linear assignment
std::vector<int> array(SIZE_ARRAY);

for (int i = 0; i < SIZE_ARRAY; ++i) {
  array[i] = i;
}

让我们分析一下这个简单的循环:

• 首先，我们需要选择输入relative 来计算我们的复杂度函数。这种情况非常简单:变量是数组的大小。那是因为我们想知道我们的程序如何响应输入数组大小的增长。

• 循环将重复 SIZE_ARRAY 次。所以主体将被执行的次数是 SIZE_ARRAY 次(注意:值是可变的，不是常量值)。

• 现在考虑循环体。 array[i] = i 指令不依赖于数组的大小。它需要未知数量的 CPU 周期，但该数量始终相同，即常量。

总而言之，我们重复 SIZE_ARRAY 次指令，该指令占用恒定数量的 CPU 时钟(假设 k 是该值，是常数)。

因此，从数学上讲，该简单程序执行的 CPU 时钟数将为 SIZE_ARRAY * k。

随着O Big notation我们可以描述限制行为。这是自变量趋于无穷大时函数将采取的行为。

我们可以这样写:

O(SIZE_ARRAY * k) = O(SIZE_ARRAY)

那是因为 k 是一个常量值，根据 Big O Notation 的定义，该常量不会增长到无穷大(永远是常量)。

如果我们将 SIZE_ARRAY 称为 N(输入的大小)，我们可以说我们的函数是一个 O(N)时间复杂度。

---

最后一个(“更复杂”)的例子:

for (int i = 0; i < SIZE_ARRAY; ++i) {
  for (int j = 0; j < SIZE_ARRAY; ++j) {
    array[j] += j; 
  }
}

如前所述，我们的问题大小与 SIZE_ARRAY 进行了比较。

很快:

• 第一个循环将执行 SIZE_ARRAY 次，即 O(SIZE_ARRAY)。
• 第二个循环将执行 SIZE_ARRAY 次。
• 第二个周期的主体是一条指令，它将占用一个固定数量的 CPU 周期，假设这个数字是 k。

我们将执行第一个循环的次数乘以循环体的复杂度。

O(SIZE_ARRAY) * [first_loop_body_complexity].

但是第一个循环的主体是:

for (int j = 0; j < SIZE_ARRAY; ++j) {
    array[j] += j; 
}

和前面的例子一样是单循环，我们刚刚计算的是复杂度。它是一个 O(SIZE_ARRAY)。所以我们可以看到:

[first_loop_body_complexity] = O(SIZE_ARRAY)

最后，我们整个的复杂度是:

O(SIZE_ARRAY) * O(SIZE_ARRAY) = O(SIZE_ARRAY * SIZE_ARRAY)

也就是

O(SIZE_ARRAY^2)

使用 N 而不是 SIZE_ARRAY。

O(N^2)