アルゴリズム推定
少し前に、モスクワのライセウムでアルゴリズムの理論の基礎を教えるように申し出られました。 もちろん、私は喜んで同意しました。 月曜日は、アルゴリズムの複雑さを評価する方法をみんなに説明しようとした最初の講義でした。 Habrの読者の中には、この情報も役立つか、少なくとも興味深いものになると思います。
アルゴリズムの複雑さを測定する方法はいくつかあります。 プログラマは通常、アルゴリズムの速度に焦点を合わせますが、他の指標も同様に重要です-メモリの量、ディスク上の空き領域の要件。 コンピューターが動作しなければならないよりも多くのメモリを必要とする場合、高速アルゴリズムを使用しても期待される結果にはなりません。
多くのアルゴリズムでは、メモリサイズと速度を選択できます。 この問題は、大量のメモリを使用して迅速に解決することも、より遅く、より少ない量を使用して解決することもできます。
この場合の典型的な例は、最短パス検索アルゴリズムです。 市の地図をネットワーク形式で提示することにより、このネットワークの任意の2点間の最短距離を決定するアルゴリズムを作成できます。 必要なときにこれらの距離を計算しないように、すべてのポイント間の最短距離を表示し、結果をテーブルに保存できます。 与えられた2点間の最短距離を見つける必要がある場合、テーブルから最終距離を取得するだけです。
結果はすぐに取得されますが、大量のメモリが必要になります。 大都市の地図には、何万もの地点を含めることができます。 次に、上記の表には100億個を超えるセルが含まれます。 つまり アルゴリズムのパフォーマンスを改善するには、追加の10 GBのメモリを使用する必要があります。
この依存性から、時空の複雑さのアイデアが流れます。 このアプローチでは、実行速度の観点と消費メモリの観点の両方からアルゴリズムが評価されます。
時間的な複雑さに焦点を当てますが、それでも、消費されるメモリの量を明確に規定します。
異なるアルゴリズムを比較する場合、その複雑さが入力データの量にどのように依存するかを知ることが重要です。 たとえば、1つの方法を使用してソートする場合、1000個の数字の処理には1秒かかります。100万個の数字の処理には10秒かかります。別のアルゴリズムを使用すると、2秒かかります。 そして5秒。 それに応じて。 このような状況では、どのアルゴリズムが優れているかを明確に言うことは不可能です。
一般的な場合、アルゴリズムの複雑さは大きさの順に推定できます。 入力データNの次元が増加するにつれて、アルゴリズムの実行時間が関数f（N）と同じ速度で増加する場合、アルゴリズムは複雑度O（f（n））を持ちます。 行列A [NxN]の各行で最大要素を見つけるコードを考えてください。
このアルゴリズムでは、変数iは1からNに変化します。iが変化するたびに、変数jも1からNに変化します。外側のループのN回の反復中に、内側のループもN回実行されます。 内部ループの反復の総数はN * Nです。 これにより、O（N ^ 2）アルゴリズムの複雑さが決まります。
アルゴリズムの複雑さの順序を推定するには、最も速く成長する部分のみを使用する必要があります。 デューティサイクルは式N ^ 3 + Nで記述されると仮定します。 この場合、その複雑さはO（N ^ 3）に等しくなります。 関数の急速に成長している部分を考慮すると、Nの増加に伴うアルゴリズムの動作を評価できます。たとえば、N = 100の場合、N ^ 3 + N = 1000100とN = 1000000の差は100のみで、0.01％です。
Oを計算するとき、式の定数因子を無視できます。 3N ^ 3の作業ステップを持つアルゴリズムは、O（N ^ 3）と見なされます。 これにより、問題のサイズの変化に対するO（N）比の依存性がより明確になります。
プログラムの最も複雑な部分は、通常、プロシージャのループと呼び出しです。 前の例では、2つのサイクルを使用してアルゴリズム全体が実行されました。
あるプロシージャが別のプロシージャを呼び出す場合、後者の複雑さをより慎重に評価する必要があります。 特定の数の命令が実行されている場合（印刷など）、これは実際には複雑性の評価に影響しません。 呼び出されたプロシージャでO（N）ステップが実行されると、関数はアルゴリズムを大幅に複雑にする可能性があります。 ループ内でプロシージャが呼び出されると、効果はさらに大きくなります。
例として、2つの手順を検討します。複雑度Oで低速（N ^ 3）と複雑度Oで高速（N ^ 2）です。
高速手順の内部サイクルで低速手順が呼び出されると、手順の複雑さが増します。 この場合、アルゴリズムの複雑さはO（N ^ 2）* O（N ^ 3）= O（N ^ 5）です。
メインプログラムが順番にプロシージャを呼び出す場合、それらの難しさは合計されます：O（N ^ 2）+ O（N ^ 3）= O（N ^ 3）。 次のスニペットには、まさにそのような複雑さがあります。
再帰プロシージャは、それ自体を呼び出すプロシージャであることを思い出してください。 彼らの難しさを判断するのは非常に難しい。 これらのアルゴリズムの複雑さは、内部ループの複雑さだけでなく、再帰の反復回数にも依存します。 再帰的な手順は非常に単純に見えるかもしれませんが、それ自体を繰り返し呼び出すことにより、プログラムを深刻に複雑にすることができます。
階乗計算の再帰的な実装を考えます：
この手順はN回実行されるため、このアルゴリズムの計算の複雑さはO（N）です。
自身を複数回呼び出す再帰アルゴリズムは、多重再帰と呼ばれます。 このような手順は分析するのがはるかに難しく、さらに、アルゴリズムがはるかに複雑になる可能性があります。
次の手順を検討してください。
この手順は2回呼び出されるため、そのデューティサイクルはO（2N）= O（N）であると想定できます。 しかし実際には、状況ははるかに複雑です。 このアルゴリズムを注意深く調べると、その複雑さがO（2 ^（N + 1）-1）= O（2 ^ N）であることが明らかになります。 再帰アルゴリズムの複雑さを分析することは非常に重要な作業であることを常に覚えておく必要があります。
すべての再帰アルゴリズムでは、ボリュームの複雑さの概念が非常に重要です。 各呼び出しで、プロシージャは少量のメモリを要求しますが、この量は再帰呼び出し中に大幅に増加する可能性があります。 このため、少なくとも再帰的手順の体積の複雑さの表面的な分析を行うことが常に必要です。
アルゴリズムの複雑さを評価することは、アルゴリズムの複雑さの上限です。 プログラムの複雑さが非常に大きい場合、これはアルゴリズムが本当に長く実行されることを意味しません。 一部のデータセットでは、アルゴリズムの実行にかかる時間は、その複雑さに基づいて想定される時間よりはるかに短くなります。 たとえば、ベクトルAの特定の要素を検索するコードを考えます。
目的の項目がリストの最後にある場合、プログラムはNステップを実行する必要があります。 この場合、アルゴリズムの複雑さはO（N）です。 この最悪の場合、アルゴリズムの実行時間は最大になります。
一方、目的のアイテムはリストの最初の位置にある場合があります。 アルゴリズムは1つのステップのみを実行する必要があります。 このような場合は最良と呼ばれ、その複雑さはO（1）と推定できます。
これらの両方のケースは考えられません。 期待されるオプションに最も関心があります。 リストアイテムが最初にランダムに混在している場合、目的のアイテムはリストのどこにでも表示できます。 必要なアイテムを見つけるには、平均してN / 2回の比較が必要です。 したがって、このアルゴリズムの複雑さは平均してO（N / 2）= O（N）です。
この場合、平均と予想される複雑さは同じですが、多くのアルゴリズムでは、最悪の場合は予想とは非常に異なります。 たとえば、最悪のクイックソートアルゴリズムにはO（N ^ 2）の次数の複雑さがありますが、予想される動作はO（N * log（N））の推定値で記述され、はるかに高速です。
次に、複雑さの計算に最もよく使用されるいくつかの関数をリストします。 関数は、複雑さの昇順でリストされています。 このリスト内の関数が高ければ高いほど、そのような推定値を持つアルゴリズムがより速く実行されます。
1. Cは定数です
2.log（ログ（N））
3.log（N）
4. N ^ C、0 <C <1
5. N
6. N *ログ（N）
7. N ^ C、C> 1
8. C ^ N、C> 1
9. N！
複雑さの方程式にこれらの関数のいくつかが含まれるアルゴリズムの複雑さを評価したい場合、方程式は表の下にある関数に還元できます。 たとえば、O（log（N）+ N！）= O（N！）。
アルゴリズムが少量のデータに対してめったに呼び出されない場合、O（N ^ 2）の複雑さは許容できると見なされますが、アルゴリズムがリアルタイムで機能する場合、O（N）のパフォーマンスは必ずしも十分ではありません。
通常、複雑度N * log（N）のアルゴリズムは適切な速度で動作します。 複雑さN ^ Cのアルゴリズムは、Cの小さな値に対してのみ使用できます。関数C ^ NおよびNによって順序が決定されるアルゴリズムの計算の複雑さ！ 非常に大きいため、このようなアルゴリズムは少量のデータを処理するためにのみ使用できます。
結論として、1秒あたり100万回の操作を実行するコンピューターが低速アルゴリズムを実行する時間を示す表を提示します。
アルゴリズムの複雑さを測定する方法はいくつかあります。 プログラマは通常、アルゴリズムの速度に焦点を合わせますが、他の指標も同様に重要です-メモリの量、ディスク上の空き領域の要件。 コンピューターが動作しなければならないよりも多くのメモリを必要とする場合、高速アルゴリズムを使用しても期待される結果にはなりません。
メモリまたは時間
多くのアルゴリズムでは、メモリサイズと速度を選択できます。 この問題は、大量のメモリを使用して迅速に解決することも、より遅く、より少ない量を使用して解決することもできます。
この場合の典型的な例は、最短パス検索アルゴリズムです。 市の地図をネットワーク形式で提示することにより、このネットワークの任意の2点間の最短距離を決定するアルゴリズムを作成できます。 必要なときにこれらの距離を計算しないように、すべてのポイント間の最短距離を表示し、結果をテーブルに保存できます。 与えられた2点間の最短距離を見つける必要がある場合、テーブルから最終距離を取得するだけです。
結果はすぐに取得されますが、大量のメモリが必要になります。 大都市の地図には、何万もの地点を含めることができます。 次に、上記の表には100億個を超えるセルが含まれます。 つまり アルゴリズムのパフォーマンスを改善するには、追加の10 GBのメモリを使用する必要があります。
この依存性から、時空の複雑さのアイデアが流れます。 このアプローチでは、実行速度の観点と消費メモリの観点の両方からアルゴリズムが評価されます。
時間的な複雑さに焦点を当てますが、それでも、消費されるメモリの量を明確に規定します。
注文評価
異なるアルゴリズムを比較する場合、その複雑さが入力データの量にどのように依存するかを知ることが重要です。 たとえば、1つの方法を使用してソートする場合、1000個の数字の処理には1秒かかります。100万個の数字の処理には10秒かかります。別のアルゴリズムを使用すると、2秒かかります。 そして5秒。 それに応じて。 このような状況では、どのアルゴリズムが優れているかを明確に言うことは不可能です。
一般的な場合、アルゴリズムの複雑さは大きさの順に推定できます。 入力データNの次元が増加するにつれて、アルゴリズムの実行時間が関数f（N）と同じ速度で増加する場合、アルゴリズムは複雑度O（f（n））を持ちます。 行列A [NxN]の各行で最大要素を見つけるコードを考えてください。
for i:=1 to N do
begin
max:=A[i,1];
for j:=1 to N do
begin
if A[i,j]>max then
max:=A[i,j]
end;
writeln(max);
end;
このアルゴリズムでは、変数iは1からNに変化します。iが変化するたびに、変数jも1からNに変化します。外側のループのN回の反復中に、内側のループもN回実行されます。 内部ループの反復の総数はN * Nです。 これにより、O（N ^ 2）アルゴリズムの複雑さが決まります。
アルゴリズムの複雑さの順序を推定するには、最も速く成長する部分のみを使用する必要があります。 デューティサイクルは式N ^ 3 + Nで記述されると仮定します。 この場合、その複雑さはO（N ^ 3）に等しくなります。 関数の急速に成長している部分を考慮すると、Nの増加に伴うアルゴリズムの動作を評価できます。たとえば、N = 100の場合、N ^ 3 + N = 1000100とN = 1000000の差は100のみで、0.01％です。
Oを計算するとき、式の定数因子を無視できます。 3N ^ 3の作業ステップを持つアルゴリズムは、O（N ^ 3）と見なされます。 これにより、問題のサイズの変化に対するO（N）比の依存性がより明確になります。
難易度の定義
プログラムの最も複雑な部分は、通常、プロシージャのループと呼び出しです。 前の例では、2つのサイクルを使用してアルゴリズム全体が実行されました。
あるプロシージャが別のプロシージャを呼び出す場合、後者の複雑さをより慎重に評価する必要があります。 特定の数の命令が実行されている場合（印刷など）、これは実際には複雑性の評価に影響しません。 呼び出されたプロシージャでO（N）ステップが実行されると、関数はアルゴリズムを大幅に複雑にする可能性があります。 ループ内でプロシージャが呼び出されると、効果はさらに大きくなります。
例として、2つの手順を検討します。複雑度Oで低速（N ^ 3）と複雑度Oで高速（N ^ 2）です。
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{- }
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
Slow;
end;
procedure Both;
begin
Fast;
end;
高速手順の内部サイクルで低速手順が呼び出されると、手順の複雑さが増します。 この場合、アルゴリズムの複雑さはO（N ^ 2）* O（N ^ 3）= O（N ^ 5）です。
メインプログラムが順番にプロシージャを呼び出す場合、それらの難しさは合計されます：O（N ^ 2）+ O（N ^ 3）= O（N ^ 3）。 次のスニペットには、まさにそのような複雑さがあります。
procedure Slow;
var
i,j,k: integer;
begin
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
{- }
end;
procedure Fast;
var
i,j: integer;
begin
for i:=1 to N do
for j:=1 to N do
{- }
end;
procedure Both;
begin
Fast;
Slow;
end;
再帰アルゴリズムの複雑さ
単純な再帰
再帰プロシージャは、それ自体を呼び出すプロシージャであることを思い出してください。 彼らの難しさを判断するのは非常に難しい。 これらのアルゴリズムの複雑さは、内部ループの複雑さだけでなく、再帰の反復回数にも依存します。 再帰的な手順は非常に単純に見えるかもしれませんが、それ自体を繰り返し呼び出すことにより、プログラムを深刻に複雑にすることができます。
階乗計算の再帰的な実装を考えます：
function Factorial(n: Word): integer;
begin
if n > 1 then
Factorial:=n*Factorial(n-1)
else
Factorial:=1;
end;
この手順はN回実行されるため、このアルゴリズムの計算の複雑さはO（N）です。
多重再帰
自身を複数回呼び出す再帰アルゴリズムは、多重再帰と呼ばれます。 このような手順は分析するのがはるかに難しく、さらに、アルゴリズムがはるかに複雑になる可能性があります。
次の手順を検討してください。
procedure DoubleRecursive(N: integer);
begin
if N>0 then
begin
DoubleRecursive(N-1);
DoubleRecursive(N-1);
end;
end;
この手順は2回呼び出されるため、そのデューティサイクルはO（2N）= O（N）であると想定できます。 しかし実際には、状況ははるかに複雑です。 このアルゴリズムを注意深く調べると、その複雑さがO（2 ^（N + 1）-1）= O（2 ^ N）であることが明らかになります。 再帰アルゴリズムの複雑さを分析することは非常に重要な作業であることを常に覚えておく必要があります。
再帰的アルゴリズムの体積の複雑さ
すべての再帰アルゴリズムでは、ボリュームの複雑さの概念が非常に重要です。 各呼び出しで、プロシージャは少量のメモリを要求しますが、この量は再帰呼び出し中に大幅に増加する可能性があります。 このため、少なくとも再帰的手順の体積の複雑さの表面的な分析を行うことが常に必要です。
ミディアムおよびワーストケース
アルゴリズムの複雑さを評価することは、アルゴリズムの複雑さの上限です。 プログラムの複雑さが非常に大きい場合、これはアルゴリズムが本当に長く実行されることを意味しません。 一部のデータセットでは、アルゴリズムの実行にかかる時間は、その複雑さに基づいて想定される時間よりはるかに短くなります。 たとえば、ベクトルAの特定の要素を検索するコードを考えます。
function Locate(data: integer): integer;
var
i: integer;
fl: boolean;
begin
fl:=false; i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true
else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
目的の項目がリストの最後にある場合、プログラムはNステップを実行する必要があります。 この場合、アルゴリズムの複雑さはO（N）です。 この最悪の場合、アルゴリズムの実行時間は最大になります。
一方、目的のアイテムはリストの最初の位置にある場合があります。 アルゴリズムは1つのステップのみを実行する必要があります。 このような場合は最良と呼ばれ、その複雑さはO（1）と推定できます。
これらの両方のケースは考えられません。 期待されるオプションに最も関心があります。 リストアイテムが最初にランダムに混在している場合、目的のアイテムはリストのどこにでも表示できます。 必要なアイテムを見つけるには、平均してN / 2回の比較が必要です。 したがって、このアルゴリズムの複雑さは平均してO（N / 2）= O（N）です。
この場合、平均と予想される複雑さは同じですが、多くのアルゴリズムでは、最悪の場合は予想とは非常に異なります。 たとえば、最悪のクイックソートアルゴリズムにはO（N ^ 2）の次数の複雑さがありますが、予想される動作はO（N * log（N））の推定値で記述され、はるかに高速です。
一般的な難易度評価機能
次に、複雑さの計算に最もよく使用されるいくつかの関数をリストします。 関数は、複雑さの昇順でリストされています。 このリスト内の関数が高ければ高いほど、そのような推定値を持つアルゴリズムがより速く実行されます。
1. Cは定数です
2.log（ログ（N））
3.log（N）
4. N ^ C、0 <C <1
5. N
6. N *ログ（N）
7. N ^ C、C> 1
8. C ^ N、C> 1
9. N！
複雑さの方程式にこれらの関数のいくつかが含まれるアルゴリズムの複雑さを評価したい場合、方程式は表の下にある関数に還元できます。 たとえば、O（log（N）+ N！）= O（N！）。
アルゴリズムが少量のデータに対してめったに呼び出されない場合、O（N ^ 2）の複雑さは許容できると見なされますが、アルゴリズムがリアルタイムで機能する場合、O（N）のパフォーマンスは必ずしも十分ではありません。
通常、複雑度N * log（N）のアルゴリズムは適切な速度で動作します。 複雑さN ^ Cのアルゴリズムは、Cの小さな値に対してのみ使用できます。関数C ^ NおよびNによって順序が決定されるアルゴリズムの計算の複雑さ！ 非常に大きいため、このようなアルゴリズムは少量のデータを処理するためにのみ使用できます。
結論として、1秒あたり100万回の操作を実行するコンピューターが低速アルゴリズムを実行する時間を示す表を提示します。
All Articles