C++での時間計算量分析に関する実践的な質問

時間計算量 任意のアルゴリズムのは、アルゴリズムが完了するのにかかる時間です。アルゴリズムの効率を示し、比較分析を行うための重要な指標です。アルゴリズムの時間計算量を減らして、より効果的にする傾向があります。

例1

次のコードスニペットの時間計算量を見つけます

for(i= 0 ; i < n; i++){
   cout<< i << " " ;
   i++;
}

ループの最大値はnですが、forループではiが2回インクリメントされるため、時間が半分になります。したがって、時間計算量はO（n / 2）であり、これはO（n）と同等です。

例2

次のコードスニペットの時間計算量を見つけます

for(i= 0 ; i < n; i++){
   for(j = 0; j<n ;j++){
      cout<< i << " ";
   }
}

内側のループと外側のループは両方ともn回実行されています。したがって、iの単一値の場合、jはn回ループし、iのn値の場合、jは合計n * n=nを2回ループします。したがって、時間計算量はO（n 2）です。

例3

次のコードスニペットの時間計算量を見つけます

int i = n;
while(i){
   cout << i << " ";
   i = i/2;
}

この場合、各反復の後、iの値は前の値の半分になります。したがって、シリーズは次のようになります。したがって、時間計算量はO（log n）です。

例4

次のコードスニペットの時間計算量を見つけます

if(i > j ){
   j>23 ? cout<<j : cout<<i;
}

コードには2つの条件ステートメントがあります。各条件文の時間計算量はO（1）であり、そのうちの2つはO（2）であり、これは定数であるO（1）と同等です。 。

例5

次のコードスニペットの時間計算量を見つけます

for(i= 0; i < n; i++){
   for(j = 1; j < n; j = j*2){
      cout << i << " ";
   }
}

内側のループは（log n）回実行されており、外側のループはn回実行されています。したがって、iの単一値の場合、jは（log n）回実行され、iのn値の場合、jは合計n *（log n）=（n log n）回ループします。したがって、時間計算量はO（n log n）です。