アルゴリズムの時間計算量と空間計算量について解説
全く同じ処理を行う2つのプログラムを想像してみてください。それぞれに1000件のレコードを入力しても、違いは分かりません。しかし、10億件のレコードを入力すると、片方はEnterキーを離す前に処理を終えるのに対し、もう片方は来週の火曜日まで処理を続けているのです。
同じノートパソコン。同じデータ。両者の違いは時間計算量であり、これはアルゴリズムに入力データが増えるにつれて、その処理負荷がどれだけ速く増加するかを表す指標に過ぎない。
この用語が実際に何を意味するのか、ビッグオー記法でどのように記述されるのか、実際のコードからどのように導き出すのか、そして空間計算量がどこで関係してくるのかを解説します。そして最後に、これらすべてが宿題ではなくなり、実際にお金がかかるようになる場所、つまりスマートコントラクトについて見ていきます。
アルゴリズムの時間計算量とは何ですか？
秒単位のことは一旦忘れてください。時間計算量はステップ数を数えます。比較、代入、ちょっとした算術演算などを行い、その合計を入力サイズnの関数として記述します。
想像しうる限り最も退屈な関数はこれだ。
python def print_all(items): for item in items: print(item)
10個のアイテム？ループを10回往復。1万個？1万回往復。
作業量は入力の横を直線的に上昇していくので、O(n) と呼びます。
さて、もしかしたら各移動には1回ではなく3回の小さな操作が必要になるかもしれません。そうです、3nです。正直なところ、誰も気にしません。なぜなら、リストを2倍にすれば作業量も2倍になるからです。そして、その成長曲線こそが私たちが求めている部分なのです。正確な数値は意図的に無視されています。
だからこそ、あらゆるDSA（データ構造アルゴリズム）講座や、コーディング面接の半分は、時間計算量について徹底的に質問するのです。アルゴリズムを見ただけでその複雑さを読み取れるなら、テストしていない入力データに対してどのように動作するかを推測できます。そして、実際の運用環境では、ほとんどのデータがまさにそのようなデータなのです。
アルゴリズムの評価指標として実行時間が不適切な理由
では、タイマーを使って実行すればいいのではないでしょうか？多くの人がそうしていますし、その気持ちは理解できます。しかし、問題は、実行時間によってアルゴリズムとは全く関係のない様々な処理が引き込まれてしまうことです。
- ハードウェア。私の5年前のノートパソコンと真新しいクラウドボックスでは、同じスクリプトでも全く異なる数値が出ます。
- プログラミング言語。同じループをC言語とPythonで記述すると、10倍以上の差が出る可能性があります。
- システム負荷。バックグラウンドで何らかの更新処理が起動し、ガベージコレクタが起動し、キャッシュがコールド状態になります。結果が変動します。
- 入力データがどのようなものであっても、ほぼソート済みのデータでは高速に動作するソート処理も、シャッフルされたデータでは処理速度が著しく低下する可能性があります。
ストップウォッチは、1つの入力に対して1回の計測しかできません。100倍のデータを要求すると、何も処理できません。
ステップ数は変動しません。同じアルゴリズム、同じ入力であれば、ラックサーバー上のRustであろうと、誰かのスマートフォン上のJavaScriptであろうと、ステップ数は同じです。だからこそ、ベンチマークを行う前であれば、時間計算量は2つのソリューション間で公平な比較ができるのです。とはいえ、後からベンチマークを行うのも良いでしょう。それはまた別の問題です。
ビッグオー記法およびその他の漸近記法について解説
教科書ではこれを漸近記法と呼ぶが、実際はそれほど難しくない。nを非常に大きくして、細かいことは気にしなくなるので、定数乗数や微小な入力は消え、成長曲線だけが残る。知っておくべき漸近記法は次の3つである。
| 表記法 | それが説明する内容 | 平易な意味 | 例 |
|---|---|---|---|
| ビッグオー、O(f(n)) | 上限値 | アルゴリズムの成長速度はf(n)を超えることはない。 | 線形探索はO(n)である |
| ビッグオメガ、Ω(f(n)) | 下限値 | このアルゴリズムは少なくともf(n)の計算量を必要とする。 | 比較ソートはΩ(n log n)です |
| ビッグシータ、Θ(f(n)) | しっかりと綴じられた | 上限と下限が一致する | マージソートはΘ(n log n)です |
実際には、95%くらいの確率でビッグオー記法を目にすることになるでしょう。これは上限を設定するもので、実行時間が括弧内の数値よりも速く増加しないことを意味します。私が初めて実際の仕事でコードレビューをした時、上級開発者がネストされたループの横に「O(n²)、修正してください」と書いていましたが、これは最悪の場合の時間計算量が2乗であり、リストがこれからかなり長くなるという意味でした。
オメガとシータは主にアルゴリズム解析の大学講義で使われるもので、仕事でこれらをタイプしたのは何年も前のことだと思います。ビッグオー記法が優れているのは、会議で人々が実際に尋ねる質問、つまり「トラフィックが3倍になったら、どれほど状況が悪化するのか？」という質問に答えられるからです。
しばらくの間、私を混乱させた技術的な点が一つあります。ビッグオーは上限値に過ぎないので、厳密に言えば、O(n) 関数は O(n²) でもあります。5 フィートの人が「7 フィート未満」であるのと同じです。確かにそうですが、役に立ちません。誰もが正当化できる最も厳密な上限値を引用するので、私もそうします。
一般的な時間計算量クラスとその例
実際のコードで目にするクラスはそれほど多くなく、恐ろしいクラスを含めてもせいぜい7つ程度でしょう。n = 1,000 の場合、それぞれのクラスのコストはおおよそ以下のようになります。
| クラス | 名前 | 典型的な例 | n = 1,000 での演算 |
|---|---|---|---|
| O(1) | 絶え間ない | 配列インデックス、ハッシュテーブル検索 | 1 |
| O(log n) | 対数 | 二分探索 | 約10 |
| の上） | リニア | リストをスキャンする | 1,000 |
| O(n log n) | 線形算術 | マージソート、クイックソート（平均） | 約10,000 |
| O(n²) | 二次関数 | ネストされたループ、バブルソート | 1,000,000 |
| O(2ⁿ) | 指数関数的 | 素朴な再帰的フィボナッチ | 宇宙の原子よりも |
| の上！） | 階乗 | 力任せの出張セールスマン | さらに大きい |
O(1): 定数時間
Pythonの辞書に10個のキーがあっても1000万個のキーがあっても、キーで1つを取り出すコストはほぼ同じで、リストからアイテム[5]を読み込むコストも同様です。このフラットさが定数時間の真髄です。
O(log n): 対数時間
これらは「1から100までの数字を推測する」アルゴリズムのようなものだと私は考えています。推測するたびに、残りの半分が除外されていきます。二分探索は、ソートされたリストに対してまさにそれを行います。
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
10億個のソート済みアイテムの場合、約30回の比較で済むのに対し、それらを1つずつ手作業で処理していくと10億個すべてが必要になる可能性があり、私はそれがどうしてもおかしく思えてしまう。
O(n) および O(n log n)
線形アルゴリズムは、スプレッドシートの列から最大の数値を目視で探すのと同じように、各要素を固定回数だけ走査します。O(n log n) は、まともなソートの基準です。マージソートは、リストを単一の項目に分割し（log n レベルの分割）、マージする際に各レベルごとに 1 回線形パスを実行するため、データがソート済みでもシャッフルされていても実行時間は変わりません。
O(n²)以上
二次コードでは、ほとんどの場合、ループの中に別のループが組み込まれています。例えば、すべてのペアを比較するこの重複チェックなどがそうです。
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
指数関数的成長や階乗的成長は、はるかに厄介です。教科書に載っている再帰的なフィボナッチ数列は、同じ部分問題を何度も繰り返し解くため、nが1増えるごとに作業量がほぼ2倍になります。n=20なら気にならないでしょうが、n=60になると、夕食を作って、食べて、片付けても、まだ終わらないでしょう。
時間計算量の計算方法をステップバイステップで解説
時間計算量を計算するのに、正式な証明はほとんど必要ありません。私は頭の中で以下のリストを思い浮かべますが、これは私が目にするほとんどのコードを網羅しています。
- nを定義します。入力サイズを決定します。リストの長さ、グラフのノード数、数値の桁数などです。
- 各行の処理量を数えます。単純なステートメント（代入、比較、算術）のコストはO(1)です。
- ブロックを順番に追加します。nを対象とする 2 つのループを 1 つずつ順番に追加すると、n + n = 2n となります。
- 入れ子になったブロックを乗算します。nをループする別のループの中に n をループすると、n × n = n² となります。
- 定数項を削除します。2nは n に、500 は 1 になります。
- 最も支配的な項のみを残します。n² + n では、n が大きくなるにつれて n² の部分が他の部分を圧倒します。
簡単な計算です。計算結果は T(n) = 3n² + 5n + 2 となります。100万を代入してみましょう。3n² は 3 兆、5n は 500 万です。丸め誤差です。O(n²) としましょう。これで完了です。
1つずつ進むのではなく、飛び飛びに進むループの方が巧妙だ。
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
各ステップでnが半分になるため、このwhileループはおおよそlog₂(n)回の繰り返しで処理を終了します。これが基本的に「時間計算量がO(log n)になるのはいつか？」という問いへの答えです。各ステップで残りの部分が定数倍ずつ縮小するなら、O(log n)になります。
再帰にはもう1つのツール、つまり再帰式が必要です。マージソートは2つの半分のサイズのジョブを実行してからマージするので、T(n) = 2T(n/2) + n となります。マスター定理は、このような形状の再帰式のためのチートシートであり、この場合は O(n log n) となります。
そして、競技プログラミングでよく使う経験則として、通常のコンピュータは1秒間に約10⁸個の単純な演算を実行できます。非常に大まかな目安ですが、提出ボタンを押す前にソリューションの時間計算量を妥当に確認するには十分です。nが10⁵の場合、O(n²)は約10¹⁰回の演算なのでタイムアウトします。O(n log n)は200万回未満なので、問題なく処理できます。
最悪ケース、最良ケース、平均ケースの分析
同じアルゴリズムに異なる入力を与えると、処理量は大きく変動する可能性がある。線形探索はそれをよく示している。
- 最良のシナリオは、欲しいものがすぐ目の前にあること。一度比較すれば、すぐに除外される。
- 最悪の場合、それは一番最後に来るか、全く来ない。つまり、n回の比較が必要になる。
- 平均的なケース：どこにでも等しい確率で出現する可能性がある場合、平均してn/2回程度チェックすることになります。それでも計算量はO(n)です。
開発者に何かの「複雑さ」について尋ねると、ほぼ必ず最悪の場合の時間計算量を教えてくれるでしょう。なぜなら、その数値は計画を立てる上での目安となるからです。
APIが最悪の場合O(n)でリクエストを処理するとしましょう。これで、最も遅いリクエストの動作が把握でき、誰かが意図的にゴミデータを送信してきた場合にも対処できます。実際にこのようなことをする人はいます。攻撃者がハッシュテーブルを衝突させるキーを特定した場合、しばらくの間はそれらのキーしか見られなくなります。
最悪のシナリオがほとんど発生しない場合、平均的なケースを検討する価値があります。クイックソートはその代表例で、平均的にはO(n log n)ですが、既にソート済みのデータに対して安易にピボットを選択するとO(n²)にまで低下します。標準ライブラリは、ランダムなピボットを使用するか、再帰が疑わしいほど深くなった時点で別のソートアルゴリズムに切り替えることで、この問題を回避しています。
空間複雑度と補助空間とは何か？
アルゴリズムが消費するもう一つの要素はメモリです。空間計算量は、入力サイズが大きくなるにつれて必要となるメモリ量を追跡するもので、時間計算量と同じビッグオー記法で表されます。
そのメモリの一部は入力データそのものであり、どのように処理しても必ずコストが発生します。実際に制御できる部分は補助領域と呼ばれ、一時変数や新しい配列など、コードが動作中に割り当てる追加のデータ、そして問題が発生するまで誰も気づかないコールスタックなどが含まれます。
簡単な事例をいくつかご紹介します。
- 2つの変数を交換するには、他の操作に関係なく数個のスロットが必要なので、O(1)の補助空間が必要になります。
- n個の項目を含むリストを新しいリストにコピーするには、O(n)の追加メモリが必要になります。
- n レベルの深さまで再帰すると、n 個のフレームがスタック上に残ります。これは、配列を作成しなくても O(n) の空間になります。
私は、あるジュニア開発者が最後の問題で午後を丸一日無駄にするのを目撃しました。彼らの再帰関数はメモリを全く使っていないように見えましたが、未完了の呼び出しはすべてスタック上に待機し、より深い呼び出しが戻るのを待っていました。そして、大きな入力があると、スタックオーバーフローで全体がクラッシュしてしまったのです。
最適化の多くは、メモリと時間のトレードオフ、あるいはその逆です。メモ化は既に計算した結果をキャッシュするため、単純なフィボナッチ数列の計算時間をO(2ⁿ)からO(n)に短縮し、その代わりにO(n)のメモリを使用します。ハッシュテーブルは、バケットにスペースを費やすことで、平均検索回数をO(1)に短縮します。64GBのRAMを搭載したサーバーでは、このトレードオフは通常は明白ですが、マイクロコントローラやスマートコントラクト内では、よく考える必要があります。
一般的なデータ構造の時間計算量と空間計算量
適切なデータ構造を選択することは、ループ内の処理を細かく調整するよりも通常は効果的です。最も頻繁に使用するデータ構造の平均コストは以下のとおりです。
| データ構造 | アクセス | 検索 | 入れる | 消去 | 空間 |
|---|---|---|---|---|---|
| 配列 | O(1) | の上） | の上） | の上） | の上） |
| リンクリスト | の上） | の上） | O(1) | O(1) | の上） |
| ハッシュテーブル | 該当なし | O(1) | O(1) | O(1) | の上） |
| バランスの取れた二分探索木 | O(log n) | O(log n) | O(log n) | O(log n) | の上） |
| バイナリヒープ | 最小値/最大値の場合はO(1) | の上） | O(log n) | O(log n) | の上） |
補足が2つあります。リンクリストの挿入と削除は、既にノードを保持している場合にのみO(1)になります。また、ハッシュテーブルは、多数のキーが衝突するとO(n)まで計算量が減少する可能性があります。
ソートアルゴリズムも同様に多様である。
| ソートアルゴリズム | 最高 | 平均 | 最悪 | 補助スペース |
|---|---|---|---|---|
| バブルソート | の上） | O(n²) | O(n²) | O(1) |
| マージソート | O(n log n) | O(n log n) | O(n log n) | の上） |
| クイックソート | O(n log n) | O(n log n) | O(n²) | O(log n) |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) |
マージソートは予測可能であるが、余分なメモリを必要とする。ヒープソートはインプレースでソートを行い、最悪の場合の計算量は変わらない。クイックソートは上限値が大きいものの、実際には優位に立つ傾向がある。
ブロックチェーンとスマートコントラクトにおける時間計算量
ここからが面白いところです。自分のサーバー上では、ずさんなアルゴリズムはCPUを浪費し、ユーザーをイライラさせるだけかもしれません。しかし、イーサリアムやその他のEVMチェーン上では、お金の無駄遣いになります。スマートコントラクトが実行するオペコードごとに、チェーンのネイティブコインで支払われるガス代が発生するため、その操作回数は誰かの請求書に一行として表示されます。つまり、時間計算量の悪さには代償が伴うのです。
報酬を支払うために、すべてのトークン保有者をループ処理するコントラクトがあるとします。計算量はO(n)で、新しい保有者が増えるごとにガス代が徐々に増加します。ローンチ当日は誰も気づきません。
そして、保有者リストは増え続ける。ある日、支払いに必要なガス量がブロックガスリミット（1つのブロックに収容できるガス量の上限）を超えると、トランザクションは実行できなくなる。「処理が遅い」というレベルではなく、単に成功しないのだ。そして、その処理の背後で待機していた資金は、事実上、滞留してしまう。監査人は、このような際限のないループをサービス拒否攻撃として報告するが、それは当然のことだ。
解決策は、単純明快に言えば、複雑性思考である。
- 作業を複数のトランザクションにわたって、固定サイズのバッチに分割する。
- 仕組みを逆にして、各ユーザーが自分の報酬を請求するようにします。呼び出しはすべてO(1)です。
- ループをマークル証明に置き換えます。
私は、log n がオンチェーンでなぜそれほど重要なのかを示す例として、マークル証明が大好きです。マークルツリーは、大量のデータをハッシュ化して、1つのルートハッシュを生成します。
あるエントリがn個のエントリの集合に属することを証明するには、約log₂(n)個のハッシュが必要です。100万個のエントリの場合、必要なハッシュ数は約20個です。100万個ではありません。エアドロップはこの仕組みを利用しており、軽量ビットコインウォレットも同様の手法を用いて、ブロック全体をダウンロードすることなくトランザクションを検証しています。
オフチェーンでも同じことが言えます。例えば、すべての未決済の請求書をスキャンして、受信したブロックチェーン取引をそれぞれ対応する請求書と照合する決済バックエンドを想像してみてください。1件の決済につきO(n)の処理が必要となり、店舗の規模が大きくなるにつれて処理速度は低下します。請求書をアドレスまたはIDをキーとするハッシュマップに格納すれば、各照合処理はO(1)になります。また、こうしたシステム構築や管理を自分で行いたくない場合は、 Plisioのような暗号通貨決済ゲートウェイを利用すれば、すべて自動で処理してくれます。
