3

この例では、2 つの個別の for ループがあります。実行時間は O(num1 + num2) ですか?

for(int i=0; i< num1 ; i++)     
{
   print i;
}

for(int i=0 ; i<num2 ; i++)
{
    print i;
}

この例では、ネストされた for ループがあります。0 から num1 までの各数値について、0 から num2 まで繰り返す必要があるため、実行時間は O(num1*num2) になりますか?

 for(int i=0 ; i<num1 ; i++)
 {
     for(int j=0 ; j<num2 ; j++)
     {  
         print i;
     }
}
4

1 に答える 1

4

より一般的になることができます。Big-O 記法は、実際のパラメーターを指定して正確な値を見つけることではありません。漸近的な実行時間を決定することです。この場合、num1 と num2 を n に置き換えることができます。ここで、n は 0 から始まる間隔の上限です。この方法を使用すると、最初の例の実行時間が O(n) であり、2 番目の例が O(n) であることがわかります。例では、実行時間が O(n^2) になります。最初の例は線形時間で実行され、2 番目の例は 2 次です。アルゴリズムのランタイムを分類するために、これ以上詳しく説明する必要はほとんどありません。

于 2013-03-28T03:05:31.523 に答える