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

アルゴリズムの歩数法

ステップカウント法は、アルゴリズムを分析する方法の1つです。この方法では、1つの命令が実行されている回数をカウントします。そこから、アルゴリズムの複雑さを見つけようとします。

シーケンシャル検索を実行するアルゴリズムが1つあるとします。各命令がc1、c2、…を取ると仮定します。実行に時間がかかる場合は、このアルゴリズムの時間計算量を調べます

アルゴリズム 回数 コスト
seqSearch（arr、n、key）
i：=0
i arr [i] =keyの場合、
壊す
終了する場合
終わり
私を返す
1
n + 1
n
0/1



1 		c1
c2
c3
c4



c5

ここで、実行回数を掛けてコストを加算すると（最悪の場合を考慮して）、次のようになります

コスト=c1+（n + 1）c 2 + nc3 + c 4 + c 5

コスト=c1+ nc 2 + c2 + nc 3 + c 4 + c5

コスト=n（c 2 + c3）+ c 1 + c 4 + c5

コスト=n（c 2 + c3）+ C

c1 + c4 + c5がCであると考えると、最終的な方程式は直線y =mx+bのようになります。したがって、関数は線形であると言えます。複雑さはO（n）になります。


  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 ∞ ∞ ∞ &