C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++での興味深い時間計算量の質問

時間計算量 アルゴリズムが平均的なケースを実行するのに必要な時間として定義できます。

いくつかの基本的な関数の時間計算量を見て計算してみましょう。

メソッド

void counter(int n){
   for(int i = 0 ; i < n ; i++){
      for(int j = 1 ; j<n ; j += i ){
         cout<<i<<” ”<<j;
      }
      cout<<endl;
   }
}

上記のメソッドは、iのすべての値に対してn/I回実行されます。つまり、最初の反復でn回、最後の反復で1回です。

これによると、合計時間計算量は

(n/1 + n/2 + n/3 + …. + n/n)
= n (1/1 + ½ + ⅓ + …. 1/n)

これで、（1/1+½+⅓+….1/ n）の値は O（log n）に等しくなります。 。

このコードの時間計算量はO（nlogn） 。

メソッド

void counter(n){
   int i , j ;
   for(int i = 1 ; i <= n ; i++){
      for(j = 1; j <= log(i) ; j++){
         cout<<i<<” ”<<j;
      }
   }
}

関数の全体的な複雑さは、O（log 1）+ O（log 2）+ O（log 3）+…です。 + O（log n！）はO（log n！）です。


  1. 漸近的な複雑さ

    漸近解析 漸近解析を使用すると、入力サイズに基づいてアルゴリズムのパフォーマンスについてのアイデアを得ることができます。正確な実行時間を計算する必要はありませんが、実行時間と入力サイズの関係を見つける必要があります。入力のサイズが大きくなるときは、実行時間を追跡する必要があります。 スペースの複雑さについては、アルゴリズムを完了するためにメインメモリ内のどのくらいのスペースが占有されているかという関係または関数を取得することが目標です。 漸近的振る舞い 関数の場合f（n） 漸近的な振る舞いは、nが大きくなるにつれてf（n）が大きくなることです。小さい入力値は考慮されません。私たちの仕事は

  2. C /C++でのバークレーのアルゴリズム

    バークレーのアルゴリズムは、分散システムのクロック同期に使用されるアルゴリズムです。このアルゴリズムは、分散ネットワークの一部またはすべてのシステムにこれらの問題のいずれかがある場合に使用されます- A.マシンには正確なタイムソースがありません。 B.ネットワークまたはマシンにUTCサーバーがありません。 分散システム 物理的に分離されているが、ネットワークを使用して相互にリンクされている複数のノードが含まれています。 バークレーのアルゴリズム このアルゴリズムでは、システムはノードをマスター/リーダーノードとして選択します。これは、サーバーのプールノードから実行され