アルゴリズムの効率性を評価する方法にはいくつかのアプローチがあります。本稿では、時間計算量の基本的な概念と解析方法について詳しく解説します。
アルゴリズム効率性の評価手法
事後統計的方法
事後統計的方法では、実際にプログラムを開発し、異なるアルゴリズムで実装されたプログラムの実行時間を計測して比較します。しかし、この方法には明らかな欠点があります：
- 事前にプログラムを開発する必要があり、多大な時間と労力を要します。もし開発後にアルゴリズムが非効率だと判明した場合、労力が無駄になる可能性があります。
- 計測結果はコンピュータのハードウェアやソフトウェア環境に依存し、アルゴリズム自体の優劣が隠蔽されることがあります。
- テストデータの設計が困難であり、プログラムの実行時間はテストデータの规模に大きく依存します。小規模なデータでは、効率的なアルゴリズムの利点が現れにくいことがあります。
これらの欠点から、事後統計的方法は一般的に推奨されません。
事前解析的推定方法
事前解析的推定方法は、プログラム開発前に統計的手法を用いてアルゴリズムの性能を推定するものです。コンピュータ上で実行される高級言語で書かれたプログラムの実行時間は、以下の要因に依存します：
- アルゴリズムが採用する戦略と方法
- コンパイラが生成するコードの品質
- 問題の入力规模
- コンピュータが命令を実行する速度
これらの要因のうち、アルゴリズムの良さは（1）に依存し、（2）はソフトウェア、（4）はハードウェアの性能に依存します。したがって、コンピュータのハードウェアやソフトウェアに関連する要因を除けば、プログラムの実行時間はアルゴリズムの良さと問題の入力规模に依存します。
入力规模とは、問題の入力データの大きさを指します。例えば、2つの異なる加算アルゴリズムを比較してみましょう：
アルゴリズム1（ループを使用）
int i, total = 0, n = 100; // 1回実行
for (i = 1; i <= n; i++) // n+1回実行
{
total = total + i; // n回実行
}
printf("%d", total); // 1回実行
アルゴリズム2（数学的公式を使用）
int total = 0, n = 100; // 1回実行
total = (1 + n) * n / 2; // 1回実行
printf("%d", total); // 1回実行
アルゴリズム1の実行回数は1 + (n+1) + n + 1 = 2n + 3回、アルゴリズム2の実行回数は1 + 1 + 1 = 3回です。両方のアルゴリズムの最初と最後のステートメントは同じであるため、注目すべきは中間部分です。ループ全体を一つの単位とみなし、ループの前後のオーバーヘッドを無視すると、これらのアルゴリズムの実行回数の差はn回と1回です。
さらに別の例を見てみましょう：
int i, j, x = 0, total = 0, n = 100; // 1回実行
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
x++; // n*n回実行
total = total + x;
}
}
printf("%d", total); // 1回実行
この例では、iが1から100まで変化するたびに内側のループが100回実行され、x++とtotal = total + xの合計実行回数はn²（ループの前後のオーバーヘッドを無視）です。
このアルゴリズムの実行回数は、同じ入力规模n=100に対して、前の2つのアルゴリズムよりもはるかに多く、nの増加に伴って実行時間も大幅に増加します。
ここで最も信頼できる実行時間の測定方法は、実行時間に影響を与える基本操作の実行回数を計算することです。実行時間はこのカウントに比例します。
関数の漸近的増加
次に、アルゴリズムAとBのどちらが優れているかを判断してみましょう。両方のアルゴリズムの入力规模はnで、アルゴリズムAは2n+3回の操作、アルゴリズムBは3n+1回の操作を実行するとします。どちらが速いでしょうか？
正確には、一概には言えません。以下の表を見てください：
| 回数 (n) | アルゴリズムA (2n+3) | アルゴリズムA2 (2n) | アルゴリズムB (3n+1) | アルゴリズムB2 (3n) |
|---|---|---|---|---|
| 1 | 5 | 2 | 4 | 3 |
| 2 | 7 | 4 | 7 | 6 |
| 3 | 9 | 6 | 10 | 9 |
| 10 | 23 | 20 | 31 | 30 |
| 100 | 203 | 200 | 301 | 300 |
- n=1のとき、アルゴリズムAはアルゴリズムBより効率が悪い（実行回数が1回多い）。
- n=2のとき、両方のアルゴリズムの効率は同じ。
- n>2のとき、アルゴリズムAはアルゴリズムBより優れ始め、nが増加するにつれてアルゴリズムAはアルゴリズムBより優位になります（実行回数が少ない）。
結論として、アルゴリズムAは全体的にアルゴリズムBより優れています。
ここで次のような定義を与えます。入力规模nが特定の値Nを超える場合、ある関数が常に別の関数より大きくなるとき、その関数は漸近的に大きく成長すると言います。
関数の漸近的増加：2つの関数f(n)とg(n)が与えられたとき、整数Nが存在して、すべてのn>Nに対してf(n)がg(n)より常に大きい場合、f(n)はg(n)より漸近的に速く成長すると言います。
nが大きくなるにつれて、後の+3や+1は最終的なアルゴリズムの変化に影響を与えないことがわかります。例えばアルゴリズムA2とアルゴリズムB2のように、これらの加算定数は無視できます。
次の例では、アルゴリズムCは4n+8、アルゴリズムDはn²+1です：
| 回数 (n) | アルゴリズムC (4n+8) | アルゴリズムC2 (4n) | アルゴリズムD (n²+1) | アルゴリズムD2 (n²) |
|---|---|---|---|---|
| 1 | 12 | 4 | 2 | 1 |
| 2 | 16 | 8 | 5 | 4 |
| 3 | 20 | 12 | 10 | 9 |
| 10 | 48 | 40 | 101 | 100 |
| 100 | 408 | 400 | 10001 | 10000 |
| 1000 | 4008 | 4000 | 1000001 | 1000000 |
n≤3のとき、アルゴリズムCはアルゴリズムDより劣りますが、n>3になるとアルゴリズムCはアルゴリズムDより優れ始め、後にははるかに優位になります。定数を取り除いても結果は変わりません。さらに、nを掛ける定数を取り除いても結果は変わらず、アルゴリズムC2の実行回数はnの増加に伴ってアルゴリズムD2よりはるかに小さくなります。
つまり、最高次項に掛かる定数は重要ではありません。
次に、アルゴリズムEは2n²+3n+1、アルゴリズムFはn³+2n+1です：
| 回数 (n) | アルゴリズムE (2n²+3n+1) | アルゴリズムE2 (2n²) | アルゴリズムF (n³+2n+1) | アルゴリズムF2 (n³) |
|---|---|---|---|---|
| 1 | 6 | 2 | 4 | 1 |
| 2 | 15 | 8 | 13 | 8 |
| 3 | 28 | 18 | 34 | 27 |
| 10 | 231 | 200 | 1021 | 1000 |
| 100 | 20301 | 20000 | 1000201 | 1000000 |
n=1のとき、アルゴリズムEとアルゴリズムFの結果は同じですが、n>1になるとアルゴリズムEの優位性がアルゴリズムFより優位になり始め、nが大きくなるにつけて差が顕著になります。観察すると、高次項の指数が大きい関数は、nの増加に伴って結果もより速く増加します。
最後に、アルゴリズムGは2n²、アルゴリズムHは3n+1、アルゴリズムIは2n²+3n+1です：
| 回数 (n) | アルゴリズムG (2n²) | アルゴリズムH (3n+1) | アルゴリズムI (2n²+3n+1) |
|---|---|---|---|
| 1 | 2 | 4 | 6 |
| 2 | 8 | 7 | 15 |
| 5 | 50 | 16 | 66 |
| 10 | 200 | 31 | 231 |
| 100 | 20000 | 301 | 20301 |
| 1000 | 2000000 | 3001 | 2003001 |
| 10000 | 200000000 | 30001 | 200030001 |
| 100000 | 20000000000 | 300001 | 20000300001 |
| 1000000 | 2000000000000 | 3000001 | 2000003000001 |
このデータから明らかなように、nの値が大きくなるにつれて、3n+1は2n²の結果と比べられなくなり、最終的には無視できるほどになります。つまり、nの値が非常に大きくなった後、アルゴリズムGはアルゴリズムIに非常に近づきます。
結論として、アルゴリズムの効率を判断する際には、関数の定数やその他の二次的な項は無視でき、むしろ主項（最高次項）の次数に注目すべきです。
アルゴリズムの良否を判断するには、少量のデータだけでは正確な判断はできません。
先ほどの例から、アルゴリズムの主要な実行回数関数の漸近的増加性を比較すれば、あるアルゴリズムがnの増加に伴って他のアルゴリズムより優れたり、劣ったりすることが分析できます。これは事前推定方法の理論的根拠であり、アルゴリズムの時間計算量を用いてアルゴリズムの時間効率を推定するものです。
アルゴリズムの時間計算量
アルゴリズムの実行回数関数がT(n)であるとき、補助関数f(n)が存在して、nが無限大に近づくときT(n)/f(n)の値が0でない定数である場合、f(n)をT(n)の同次関数と呼び、T(n)=O(f(n))と記します。
O(f(n))をアルゴリズムの漸近的時間計算量、または単に時間計算量と呼びます。
この大文字O()を用いてアルゴリズムの時間計算量を表記する方法をBig O記法と呼びます。
一般に、nの増加に伴ってT(n)が最も遅く増加するアルゴリズムが最も優れたアルゴリズムです。
時間計算量の定義から、3つの加算アルゴリズムの時間計算量はそれぞれO(n)、O(1)、O(n²)です。これらには非公式な名称が付けられており、O(1)を定数階、O(n)を線形階、O(n²)を二乗階と呼びます。もちろん、他にもいくつかの次数がありますが、後で紹介します。
Big O次数の導出方法
アルゴリズムの時間計算量を分析し、Big O次数を導出する方法を以下に示します。基本的に、これはこれまで挙げてきた例をまとめたものです。
**Big O次数の導出方法：
- 実行回数関数のすべての加算定数を1で置き換える。
- 修正後の実行回数関数で、最高次項のみを残す。
- 最高次項が存在し、その係数が1でない場合、その項に掛かる係数を除去する。 結果がBig O次数となる。**
この導出方法は、アルゴリズムの時間計算度を導出する万能式のようです。しかし、実際にはアルゴリズムの時間計算量を分析するのはそれほど簡単ではなく、さらに多くの例を見る必要があります。
例えば、先ほどのアルゴリズムHはT(n)=3n+1、f(n)=nであり、nが無限大に近づくときT(n)/f(n)=3であるため、アルゴリズムHの時間計算量はO(n)となります。
定数階
まずは順次構造の時間計算量について説明します。
以下のアルゴリズムの時間計算量がO(3)ではなくO(1)である理由を理解しましょう。
int total = 0, n = 100; // 1回実行
total = (1 + n) * n / 2; // 1回実行
printf("%d", total); // 1回実行
このアルゴリズムの実行回数関数はf(n)=3です。Big O次数を導出する方法の第一段階として、定数項3を1に変更します。最高次項を残す際に、最高次項がないことがわかります。したがって、このアルゴリズムの時間計算量はO(1)です。
さらに、このアルゴリズムのステートメントtotal=(1+n)*n/2が10個ある場合を考えてみましょう：
int total = 0, n = 100;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
total = (1 + n) * n / 2;
printf("%d", total);
実際には、nが何であれ、上記の2つのコードの実行回数の差は3回と12回だけです。問題の规模（nの大きさ）に関係なく、実行時間が一定であるアルゴリズムは、O(1)の時間計算量を持つと呼ばれ、定数階とも呼ばれます。
注意：この定数が何であれ、O(1)と記録し、O(3)、O(12)などの他の数字にはできません。これは初心者がよく犯す間違いです。
分岐構造の場合、真偽のいずれであっても実行回数は一定であり、nの大きさが変化しても変化しません。したがって、単独の分岐構造（ループ構造内に含まれないもの）の時間計算量もO(1)です。
線形階
線形階のループ構造はさらに複雑になります。
あるアルゴリズムの次数を決定するには、特定のステートメントまたはステートメントセットの実行回数を決定する必要があります。
したがって、アルゴリズムの複雑さを分析する鍵は、ループ構造の実行状況を分析することです。
以下のコードのループ部分の時間計算量はO(n)です。なぜなら、ループ本体のコードはn回実行されるからです。
int i;
for (i = 0; i < n; i++)
{
/* 時間計算量がO(1)のステップのシーケンス */
}
対数階
次のコードの時間計算量はどのくらいでしょうか？
int count = 1;
while (count < n)
{
count *= 2;
/* 時間計算量がO(1)のステップのシーケンス */
}
countが2倍されるたびに、nに一歩近づきます。
つまり、いくつの2を掛け合わせるとnを超えるかによって、ループが終了します。
x=log₂nを得るので、このループの時間計算量はO(log n)です。
数学的な記号では、これは通常O(log₂n)またはO(log n)と書かれます。ここで、log₂nは底が2であることを明確に示していますが、log nはコンピュータ科学では一般的に底が2の対数を暗黙的に指します。これはコンピュータ科学で最も一般的な対数の底であるためです。
書く際には、読者と文脈環境に応じて底を明示するかどうかを決めるべきです。
底を強調する必要がある、または読者がこれについて疑問を抱く可能性がある場合は、O(log₂n)を使用するとより明確になります。読者がlog nが通常底が2の対数を指すことを理解していると確信できる場合は、O(log n)を使用して表現を簡略化できます。
さらに、一部のアルゴリズムの時間計算量は、他の数を底とする対数である可能性があることに注意してください。例えば、O(log₁₀n)やO(logₑn)など。
しかし、ほとんどの場合、アルゴリズム分析で対数複雑度について言及する際には、実際にはO(log₂n)または同等のO(log n)を指しています。これはコンピュータ科学で最も一般的なためです。
アルゴリズム分析において、log₂nとlog nは基本的に等価であり、どちらも底が2の対数複雑度を表します。コンピュータ科学でlog nと言及する場合、通常は底が2の対数、つまりlog₂nを暗黙的に指します。
これは、コンピュータ科学の多くのアルゴリズム、特に分割統治戦略に関連するアルゴリズム（二分探索、マージソートなど）の複雑度が、底が2の対数と関連していることが多いからです。
したがって、ほとんどの場合、log₂nとlog nは交換可能に使用できると見なせます。どちらの表記方法を使用するかは主に個人的な好みと文脈環境に依存します。底を明確にする必要がある場合は、log₂nを使用するとより明確になります。一般的な議論では、log nを使用して表現を簡略化できます。
要約すると、アルゴリズム分析におけるlog₂nとlog nは、同じ対数複雑度概念を指しており、log nはlog₂nの省略形または口語的な表現です。
二乗階
次の例はループのネストであり、内側のループはすでに分析したように、時間計算量はO(n)です。
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
/* 時間計算量がO(1)のステップのシーケンス */
}
}
外側のループは、時間計算量がO(n)のステートメントをn回繰り返すだけです。したがって、このコードの時間計算量はO(n²)です。
外側のループの回数がmに変更された場合、時間計算量はO(m×n)になります。
int i, j;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
/* 時間計算量がO(1)のステップのシーケンス */
}
}
したがって、ループの時間計算量は、ループ本体の複雑さにそのループの実行回数を掛けたものに等しいと結論付けられます。
では、このループのネストの時間計算量はどのくらいでしょうか？
int i, j;
for (i = 0; i < n; i++)
for (j = i; j < n; j++) /* j = iではなく0に注意 */
{
/* 時間計算量がO(1)のステップのシーケンス */
}
i=0のとき、内側のループはn回実行され、i=1のときはn-1回、…、i=n-1のときは1回実行されます。したがって、総実行回数はn+(n-1)+(n-2)+…+1=n(n+1)/2=n²/2+n/2です。
Big O次数を導出する方法を使用すると、
- 加算定数がないので考慮しません
- 最高次項のみを残すため、n²/2を保持します
- この項に掛かる定数を除去する、つまり1/2を除去します
最終的にこのコードの時間計算量はO(n²)です。
この例からもわかるように、Big O次数の導出を理解するのはそれほど難しくありませんが、難しいのは数列の関連演算であり、これはより多くあなたの数学的知識と能力を試すものです。
さらに例を見て、メソッド呼び出しの時間計算量を分析する方法について説明します。
int i, j;
for (i = 0; i < n; i++)
{
function(i);
}
上記のコードはfunction()という関数を呼び出しています。
void function(int count)
{
print(count);
}
関数本体はcountというパラメータを出力するだけです。これはfunction()関数の時間計算量がO(1)であることを理解するのは簡単です。
したがって、全体の時間計算量はO(n)です。
もしfunction()が次のようなものであるとします：
void function(int count)
{
int j;
for (j = count; j < n; j++)
{
/* 時間計算量がO(1)のステップのシーケンス */
}
}
実際には、これは先ほど挙げた例と同じです。ネストされた内側のループを関数内に配置しただけなので、最終的な時間計算量はO(n²)です。
以下の比較的複雑なステートメントを見てみましょう：
n++;
function(n);
int i, j;
for (i = 0; i < n; i++)
{
function(i);
}
for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
printf("hello");
}
}
その実行回数はf(n)=1+n+n²+n²/2+n/2=n²+3n/2+1です。Big O次数を導出する方法を使用すると、このコードの時間計算量もO(n²)です。
時間計算量の比較
時間計算量が消費する時間の比較は、小さいものから大きいものへ順に次のようになります：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
最悪ケースと平均ケース
朝、出勤後にスマートフォンを忘れたことに気づいたとします。今の時代、鍵、財布、スマートフォンの三大品物、どれも欠かせません。そこで帰宅して探します。ドアを開けてみると、スマートフォンは玄関のテーブルの上にありました。どうやら靴を履く時に忘れていたようです。これはもちろん良くて、ほとんど時間をかけずに見つかりました。しかし、そこになければ、中に入ってあちこち探さなければなりません。リビングを探して寝室を探して、寝室を探してキッチンを探し、キッチンを探してバスルームを探し、それでも見つからず、時間が一分一秒と過ぎていきます。突然思い出しました、家の固定電話でスマートフォンをかければ、スマートフォンの着信音に従って探せるんだと。本当に馬鹿げている。ついに見つかりました。ベッドの枕の下です。再び出勤すると、遅刻してしまいました。しまった、この年の全勤賞、スマートフォンを探したせいで台無しになったものです。
物を探すには運が良い時もあれば、どうしても見つからない時もあります。しかし、現実では、最も良いケースでも最も悪いケースでもない状況に遭遇することがほとんどです。
アルゴリズムの分析も同様です。n個のランダムな数字からなる配列から特定の数字を検索する場合、最も良いケースは最初の数字がそれであることで、アルゴリズムの時間計算量はO(1)です。しかし、その数字が最後の位置にある可能性もあります。その場合、アルゴリズムの時間計算量はO(n)となり、これは最も悪いケースです。
最悪ケースの実行時間は保証であり、それ以上悪くならないことを意味します。応用において、これは最も重要な要件です。通常、特に指定がない限り、言及される実行時間は最悪ケースの実行時間です。
平均実行時間は、確率の観点から、この数字が各位置にある可能性が同じであるため、目標要素を発見するまでの平均的な検索時間は(n+1)/2回となります。
平均実行時間はすべてのケースの中で最も意味のあるものであり、期待される実行時間です。つまり、プログラムコードを実行する際には、平均実行時間が見られることを期待します。しかし、現実には平均実行時間は分析によって得るのが難しく、通常は一定量の実験データを実行した後に推定されます。
アルゴリズムの分析には、すべてのケースの平均値を計算する方法があり、この時間計算量の計算方法を平均時間計算量と呼びます。もう一つの方法は、最悪ケースでの時間計算量を計算する方法であり、この方法を最悪時間計算量と呼びます。
通常、特に指定がない限り、最悪時間計算量を指します。