algorithm - forループの計算量 - 自分と矛盾する

Question

プログラムの実行時間を分析して矛盾があります。たとえば、次のコードを考えてみましょう。

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
         .....
    }
}

ここで、最初の for ループの計算量は O(n ² ) で、2 番目のループの計算量は O(n) です。ただし、2 番目のループは n ²回実行されますが、最初のループは n 回実行されます。たとえば、内側のループの内側に cout ステートメントを配置すると、n ²回出力されますが、最初のループの内側で内側のループの外側に cout ステートメントを配置すると、n 回出力されます。では、なぜ内側のループの複雑さを O(n) と言うのに、外側のループの複雑さを O(n ² ) と言うのでしょうか。外側のループの複雑さは O(n ² ) ですが、n 回実行されるのはなぜですか? 私は何か間違ったことをしていますか？ありがとう。

Answer 1

内側のループは n 回実行され、O(n) かかります。外側のループは内側のループを n 回実行しますが、n 回の外側のループの実行ごとに内側のループのコストを考慮する必要があります。これにより、O(n * O(n)) = O(n^2) になります。

Answer 2

外側のループは n 回実行され、内側のループは外側のループの反復ごとに n 回実行され、内側のループは n^2 回実行されます。したがって、内側のループのステートメントは n^2 回実行されます。