关于两个因环的复杂性的混乱

Question

for(i=1; i < n; i++){
   for(j=1; j <= i; j++){
         statement1;
   }       
}

• 外循环= o(n(
• 内部循环= n(n-1(/2
• 总计= n*n(n-1(/2 = n^3

似乎n^3是这些嵌套环的复杂性。但是符合书籍的规定，其复杂性是n(n-1(/2的n^2。

Answer 1

唯一有趣的事情是statement1执行一次。

因此，请注意

之类的东西

for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++)
        statement1;

触发2 * 3 = 6执行。因此，您可以计算内部循环执行每个外部环路迭代。

的频率。

但是，在您的示例中，您犯了一个错误，并将外循环的迭代乘以内部环的的总迭代，而不是迭代的数量每个外部循环迭代。

在上面的示例中，它就像2 * 6 = 12，而不是2 * 3 = 6。

---

让我们仔细看看您的特定示例中发生的情况。外环会触发内部环的n迭代。内部循环首先产生1迭代。在外循环的下一次迭代中，它将产生2迭代，然后是3等。

总共您将收到内部循环的1 + 2 + ... + n = (n^2 - n)/2迭代。同样，请注意总计中的''。因此，statement1将总计执行(n^2 - n)/2次。外循环迭代已经考虑到内循环的总运行，没有其他乘法。

---

(n^2 - n)/2显然在O(n^2)中，由于其渐近复杂性。直觉上，最大的因素起着作用，我们可以通过估计<=。

来删除其他东西。

(n^2 - n)/2
    <= n^2 - n
    <= n^2 in O(n^2)

Answer 2

1. for(i = 1; i＆lt; n; i ({
2. for(j = 1; j＆lt; = i; j ({
3. 语句1;
4. }
5. }

为了简化问题，让我们假设n在这里5。因此，第1行将执行5次，因为它将检查并增加I值5次。第2行将执行(5-1(= 4次，因为对于i = 5，它将不会执行，但第1行将对i = 5执行。第3行将执行1次，2次3次，依此类推，每次我都会递增。

将第三行的复杂性纳入上下文中，您会发现它正在执行1 2 3 4 = 10次。这只是1到4的数字之和，或者您可以说n(n 1(/2其中n = 4。我们可以忽略第1行和第2行的复杂性，因为它们是恒定的，在渐近符号中，复杂性将为O(n^2(。

Answer 3

您可以考虑2个嵌套循环，因为检查对角线上的所有单元格，在n x n矩阵上的对角线下方。

因此，您将始终执行接近n^2的1/2的许多操作。因此，代码的操作总数为n^2 *常数。按照Big-O符号的定义，这意味着您的代码运行时复杂性为O(n^2(。

这是一个简单的代码，可以帮助您了解我的解释。

#include <vector>
#include <iostream>
using std::vector;
using std::cout;
using std::endl;
// These function count the number of times that your code will execute statement1
int count(int N){
    int total = 0;
    for(int l = 0; l < N; ++l){
        for(int r = 0; r <= l; ++r){
            total++;
        }
    }
    return total;
}
// this code will show the cells of the matrix that you are "executing"
int showMatrix(int N){
    vector<vector<bool> > mat(N, vector<bool>(N, false) );
    for(int l = 0; l < N; ++l){
        for(int r = 0; r <= l; ++r){
            mat[l][r] = true;
        }
    }
    for(int line = 0; line < N; ++line){
        for(int column = 0; column < N; ++column){
            cout << (mat[line][column] == true ? "1 " : "0 ");
        }
        cout << endl;
    }
}
int main(){
    showMatrix(10);
    cout << count(10) << endl;
    return 0;
}