对两个相关循环的复杂性感到困惑?

唯一有趣的是计算频率 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 内部循环的迭代。再次注意' 总计 '. 所以 声明1 将 总计 被执行 (n^2 - n)/2 《泰晤士报》。在计算内循环的总运行次数时,已经考虑了外循环迭代,没有额外的乘法。

(n^2-n)/2 显然是在 O(n^2) 由于其渐近复杂性。直觉上,只有最大的因素起作用,我们可以通过使用 <= .

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

1. 对于(i=1;i<n;i++){
2. 对于(j=1;j<=i;j++){
3. 声明1;
4. }
5. }

为了简化这个问题,我们假设n在这里是5。 因此,第1行将执行5次,因为它将检查并增加i值5次。 第2行将执行(5-1)=4次,因为对于i=5,它将不执行,但对于i=5,第1行将执行。 第3行将执行1次、2次、3次,以此类推,每次i递增。

把第三行的复杂性放到上下文中,您会发现它正在执行1+2+3+4=10次。它只是从1到4的数字之和,或者你可以说,n(n+1)/2,其中n=4。 我们可以忽略第1行和第2行的复杂性,因为它们是常数,并且在渐近表示法中,复杂性将为O(n^2)。

可以将这两个嵌套循环视为检查nx 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;
}