Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords

algorithmアルゴリズムの複雑さ


備考

すべてのアルゴリズムは、問題を解決するためのステップのリストです。各ステップは、前のステップのいくつかのセット、またはアルゴリズムの開始に依存しています。小さな問題は次のようになります。

ここに画像の説明を入力

この構造は、有向非循環グラフ、つまりDAGと呼ばれています。グラフ内の各ノード間のリンクは、操作の順序による依存関係を表し、グラフにはサイクルが存在しません。

依存関係はどのように起こるのですか?たとえば、次のコードを考えてみましょう:

total = 0
for(i = 1; i < 10; i++)
    total = total + i

このpsuedocodeでは、forループの各反復は、前回の反復で計算された値を使用しているため、前の反復の結果に依存します。このコードのDAGは次のようになります。

ここに画像の説明を入力

アルゴリズムのこの表現を理解すれば、それを使ってアルゴリズムと複雑さを作業とスパンの観点から理解することができます。

作業

仕事は、与えられた入力サイズnアルゴリズムの目標を達成するために実行される必要がある実際の操作の数です。

スパン

スパンはクリティカルパスと呼ばれることもあり、アルゴリズムの目的を達成するためにアルゴリズムが最低限必要とするステップ数です。

次の図は、グラフを強調表示し、サンプルDAGの作業とスパンの違いを示しています。

ここに画像の説明を入力

仕事はグラフ全体のノード数です。これは、上記の左のグラフで表されます。スパンはクリティカルパス、または開始から終了までの最長パスです。作業を並行して行うことができれば、右側の黄色い強調表示されたノードはスパンであり、必要なステップの数は最も少ない。作業を連続して行わなければならない場合、そのスパンは作業と同じです。

作業とスパンの両方を分析の観点から独立して評価することができます。アルゴリズムの速度はスパンによって決まります。必要とされる計算能力の量は、作業によって決定される。

アルゴリズムの複雑さ 関連する例