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

アルゴリズムの操作カウント方法

アルゴリズムのコストを見積もるにはさまざまな方法があります。そのうちの1つは、操作カウントを使用します。さまざまな操作の1つを選択することにより、アルゴリズムの時間計算量を見積もることができます。これらは、加算、減算などのようなものです。これらの操作がいくつ実行されたかを確認する必要があります。この方法が成功するかどうかは、ほとんどの場合、複雑さの原因となる操作を特定できるかどうかにかかっています。

サイズがn[0からn-1]の配列があるとします。私たちのアルゴリズムは、最大の要素のインデックスを見つけます。配列の要素の各ペア間で実行される比較操作の数を数えることにより、コストを見積もることができます。覚えておく必要があるのは、1つの操作のみを選択することです。このアルゴリズムでは、反復変数iの増分や、インデックスの値の割り当てなど、他にいくつかの操作があります。ただし、この場合は考慮されません。

アルゴリズム 
getMax(arr, n):
   index := 0
   max := arr[0]
   for i in range 1 to n - 1, do
      if arr[i] > max, then
         max := arr[i]
         index := i
      end if
   done
   return index

コストを見積もるには、最大時間実行される操作を選択する必要があります。バブルソートアルゴリズムが1つあり、スワップ操作をカウントするとします。次に、それがいつ最大になるかを覚えておく必要があります。これにより、分析中に最大の結果が得られます。


  1. フォードファルカーソンアルゴリズム

    Ford-Fulkersonアルゴリズムは、特定のグラフの開始頂点からシンク頂点への最大フローを検出するために使用されます。このグラフでは、すべてのエッジに容量があります。 SourceとSinkという名前の2つの頂点が提供されます。ソース頂点にはすべて外向きのエッジがあり、内向きのエッジはありません。シンクにはすべて内向きのエッジがあり、外向きのエッジはありません。 いくつかの制約があります： エッジのフローは、そのグラフの所定の容量を超えません。 流入フローと流出フローも、ソースとシンクを除くすべてのエッジで等しくなります。 入力と出力 入力：隣接行列：0 10 0 10 0

  2. フロイドウォーシャルアルゴリズム

    Floyd-Warshallアルゴリズムを使用して、特定の重み付きグラフからすべてのペアの最短経路問題を見つけます。このアルゴリズムの結果として、グラフ内の任意のノードから他のすべてのノードまでの最小距離を表す行列が生成されます。 最初、出力行列はグラフの指定されたコスト行列と同じです。その後、出力行列はすべての頂点kを中間頂点として更新されます。 このアルゴリズムの時間計算量はO（V ^ 3）です。ここで、Vはグラフ内の頂点の数です。 入力と出力 Input: The cost matrix of the graph. 0 3 6 ∞ ∞ ∞ &