前書き
こんにちは、ソースコードを読むことを忘れずに1日26階を登る筋金入りの男、トンです。
ご存知のように、データ構造とアルゴリズムが解決する主な問題は、「高速化」と「省スペース化」の問題です。
従って、「高速」と「省スペース」はアルゴリズムの2つの非常に重要な指標であり、時間複雑性と空間複雑性の分析でよく耳にするものです。
では、なぜ複雑性分析が必要なのでしょうか？複雑性分析の方法論とは？
それがこのセクションで取り上げる内容です。
さて、今日の勉強に入りましょう。
なぜ複雑性分析が必要なのですか？
まず、2つのアルゴリズムについて、どちらがより速く、どちらがよりメモリ効率よく実行されるかをどのように判断するか、という問題を考えてみましょう。
2つのアルゴリズムを一度実行し、実行時間とメモリ使用量を数えてみてください。
後知恵の統計学という、とても生々しい名前がついています。
しかし、この統計的アプローチには非常に明白な問題があります：
インプットの違いが結果に大きな影響
ある入力に対してはアルゴリズムAが速く実行され、別の入力に対してはアルゴリズムBが速く実行されるかもしれません。例えば、後で学習するソートアルゴリズムでは、入力の順序が異なるソートアルゴリズムに全く異なる影響を与えます。
マシンの違いは結果に大きな影響を与えます
同じ入力に対して、あるマシンではアルゴリズムAが速く、別のマシンではアルゴリズムBが速いということがあります。例えば、アルゴリズムAがマルチコアを利用でき、アルゴリズムBが利用できない場合、CPUコアの数は2つのアルゴリズムに大きく異なる影響を与えます。
データサイズは結果に大きな影響
データサイズが小さいときはアルゴリズムAの方が速く、データサイズが大きくなるとアルゴリズムBの方が速くなる場合があります。例えば、後ほど学習するソートアルゴリズムでは、データサイズが比較的小さい場合は、サブサンプションソートよりもインサーションソートの方が高速になります。
そのため、実際にアルゴリズムを実行することなく、アルゴリズムの実行効率を推定できる手法が求められています。
これは複雑性解析としても知られています。
では、複雑性分析はどのように行うのでしょうか？そのための方法論はあるのでしょうか？
その方法論は漸近分析と呼ばれています。
漸近解析とは何ですか？
漸近解析とは、アルゴリズムの実行効率を入力の大きさに連動させる手法で、入力の大きさが大きくなるにつれて、アルゴリズムの実行に要する時間にどのような傾向が現れるか、この傾向を漸近的といい、この手法を漸近解析といいます。
簡単な例を挙げましょう。与えられた順序配列に対して、ある値の位置を見つけたい、例えば要素8を見つけたい場合、どのような方法があるでしょうか？
シンプルで暴力的なメソッドで、先頭からたどり、返された要素を見つけます。
もう少しフレンドリーな方法は、二等分法の使用は、データの真ん中を見つけるために、毎回、その値と目標値の大きさの値を参照してくださいに、それが左または右にあるかどうかを決定するために二等分する方法を見つけるために続けています。
上記の例の入力スケールは8要素の順序配列で、目標値は8です。
しかし、ルックアップのゴールが1だったらどうでしょう？
最初の方法では、ルックアップは1回で十分です。
つ目の方法では、3回のルックアップが必要です。
この時点では、2番目の方法は1番目の方法よりもまた二の次です。
したがって、2つのアルゴリズムの実行効率を比較するには、個々の要素を考慮するだけでなく、すべての要素の気持ちを考慮する必要があります。
入力サイズがnにスケールアップすると仮定して、2つの方法の平均実行効率をカウントするために数学的アプローチを使用します。
最初の方法では、要素1が1回、要素2が2回、要素3が3回......調べられ、各要素が見つかる確率は1/nです。
つまり、1x1/n + 2x1/n + 3x1/n + ...のように効率的に実行されます。 nx1/n = nx(n+1)/2/n = /2.
2番目の方法では、真ん中に1つの要素があり、それを1回見つけ、サブ・ミドルに2つの要素があり、それを2回見つけ、サブ・サブ・ミドルに4つの要素があり、それを3回見つけ...。各要素を見つける確率は1/nです。
つまり、1x1x1/n + 2x2x1/n + 4x3x1/n + ... の効率で実行されます。 + 2^-2) x -1) x 1/n+ 2^-1) x log2(n) x 1/n = ?
なんてこった、この結果は何に等しい？
本当の強さを見せる時です：
小卒の私がデータ構造とアルゴリズムを学べるわけがない、と罵られるかもしれません。
いえいえ、そんなことはありません。それについては次のセクションで。
追記
この章では、アルゴリズムの実行効率の観点から複雑性解析が必要とされる理由を説明し、複雑性解析の方法、すなわち漸近解析を紹介します。漸近解析は、厳密に従えば多くの数学的知識を必要とし、アルゴリズムの解析を難しくすることは間違いありませんが、複雑性を計算する上で、これ以上手間のかからない方法はないのでしょうか？
