アルゴリズムの基本と算法体系：計算量まで体系的に理解する

参考サイト

• 一週間で身につくアルゴリズムとデータ構造
• 計算量・漸近計算量・オーダー記法について
• 計算量における対数の使われ方
• 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜

はじめに

この記事の大まかな内容

この記事では、アルゴリズムの定義やその重要性について解説しています。
アルゴリズムはプログラミングの核となる技術であり、数学や日常生活における問題解決の基本となる概念であると述べています。
また、アルゴリズムを学ぶことで得られるメリットや、具体的な例を通じてアルゴリズムの適用方法を紹介しています。
さらに、アルゴリズムの計算量についても触れ、問題解決における効率性の重要性を強調しています。

この記事の背景

この記事は、アルゴリズムの基本的な概念や重要性を再確認し、体系的に整理することを目的としています。
プログラミングや数学の分野でアルゴリズムがどのように関連し、どのような場面で適用できるのかを考える際の指針を目指しています。
また、アルゴリズムを単なる手順として捉えるのではなく、問題解決のための考え方の枠組みとして理解することの重要性を伝えています。

この記事が役立つ人

この記事は、アルゴリズムの基礎を学びたい初心者向けに書かれています。
基本的なアルゴリズムの知識を整理しながら、体系的に理解を深める視点を提供することを意図しています。
また、アルゴリズムを幅広い視点で捉える重要性を共有し、これから新しい分野へ挑戦する際の足掛かりとしたい読者にも適しています。

1.アルゴリズムとは何でしょうか？

ことばの語源

アルゴリズムの語源は［アルゴリトミ］という本です。
正式名称は［アルゴリトミ・デ・ヌーメロ・インドルム］で［インドの数の計算法］というアラビア本のラテン語訳版です。
著者は［アル＝フワーリズミー］という人物で、９世紀前半に活躍したイスラム科学の学者です。
この本は、中世ヨーロッパ各国の大学で数学の主要な教科書として用いられました。

「アルゴリズム」という言葉を聞いたことはありますか？
日常生活ではあまり使わないかもしれませんが、実は私たちの身の回りで頻繁に使われています。

アルゴリズムとは、［問題を解決するための手順やルールの集合］です。
これはプログラミングだけでなく、数学や日常生活にも関わる重要な概念です。

本記事では、アルゴリズムの概念を体系的に整理し、その基本構造を明確にすることで、より深い理解へとつなげます。

アルゴリズムはプログラムの核

プログラミングでは、if文やfor文といった構文を使って処理を組み立てます。
その背後には、「どのようにデータを処理し、目的を達成するか」というアルゴリズムの設計が不可欠です。
つまり、アルゴリズムはプログラミングの中心的な技術なのです。

しかし、アルゴリズムはプログラマーだけのものではありません。

アルゴリズムは生活にも役立つ

実は、私たちは日々の生活でアルゴリズムを活用しています。

例えば、買い物をするとき。

• 予算を考える
• 必要なものをリスト化する
• 効率よく回るルートを決める

これらはすべて、情報を処理し最適な判断をするアルゴリズムの一例です。

アルゴリズムを学ぶメリット

アルゴリズムを学ぶと、

• 問題解決のスキルが向上する → 仕事や生活で論理的な判断ができる
• 効率的な考え方が身につく → 時間やコストを最適化できる
• 新しい分野にも応用できる → 他の知識と組み合わせて成長できる

「考え方の武器」として、アルゴリズムは誰にとっても役立つ概念なのです。

アルゴリズムの例を考えてみよう

アルゴリズムを日常の例に当てはめて考えてみましょう。
たとえば、学校の授業の順番や内容の決め方を考えてみます。

先生による授業の決め方

• アルゴリズムA：先生Aは、各生徒の理解度を テストの点数 だけで判断し、授業の順番と内容を決める。
• アルゴリズムB：先生Bは、 テストの点数に加えてアンケートの結果 も考慮し、授業の順番と内容を決める。

つまり、どの情報をもとに判断するか（＝アルゴリズム）によって、授業の進め方が変わるのです。

情報をどう処理するかがカギ

情報を集めたら、それを どのように処理するか（アルゴリズム） が重要になります。

授業の決め方の例では、

• テストの点数だけ で決める方法（アルゴリズムA）は、客観的だが個々の意見を反映しにくい。
• テスト + アンケート を使う方法（アルゴリズムB）は、生徒の意見を反映しやすいが、データの処理が複雑になる。

どちらが適しているかは 目的 によります。

生徒の学習効果を最大化するなら、どの情報を使い、どんな判断基準を設けるかがポイントになります。

アルゴリズム	判断基準	メリット	デメリット
アルゴリズムA	テストの点数	客観的な基準で判断できる	生徒の意見が反映されにくい
アルゴリズムB	テストの点数 + アンケート	生徒の意見を反映しやすい	データ処理が複雑になる

他にも様々な場面でアルゴリズムは活用されています。

例えば、スケジュール管理では「優先度の高いタスクから処理する」アルゴリズム、買い物では「予算内で最も必要なものを選ぶ」アルゴリズムが自然に働いています。

目的や状況に応じて最適なアルゴリズムを考案することで、より効率的な判断が可能になります。

算法体系

この記事では、アルゴリズムについてさまざまな視点から説明してきました。
それらを整理すると、本質的には次の問いに集約されます。

「ある目的を達成するために、どの情報をもとに判断するか？」＝［算法体系］

$\overset{\tiny さんぽうたいけい}{算法体系}$とは、算術的な手法を体系的に整理し、問題解決の枠組みとして捉える という意味を持つ造語です。このブログでは、この概念をもとに、アルゴリズムをより深く理解する視点を探ります。

算法体系という言葉を使う意図

本記事では、単なるアルゴリズムの実装手順やテクニックを紹介するのではなく、アルゴリズムを体系的に整理し、俯瞰する視点を持つことの重要性 を意識しています。

「算法体系」という言葉を用いた理由は、以下のような考えに基づいています。

---

1. アルゴリズムの関連性を意識しやすくするため

アルゴリズムを学んでいると、個別の手法（並べ替え、数値探索、再帰処理など）を理解するだけでなく、それらがどのように関連し、どのような場面で適用できるのか を考えることが重要になってきます。

「算法体系」という表現を使うことで、個々のアルゴリズムを単体で捉えるのではなく、より広い枠組みで整理する視点 を持てるのではないかと考えました。

---

2. アルゴリズムを「使う」だけでなく「考える」ため

既存のアルゴリズムを実装することに慣れた後、次の段階として「どうすればより良い解法を導き出せるか？」を考える機会が増えてきます。

自分自身、そうした思考を整理する中で、「アルゴリズムは単なる手順ではなく、問題解決のための考え方の枠組みではないか？」と感じました。

そのため、「算法体系」という表現を通じて、アルゴリズムをより深く捉えるための概念 を示したいと思っています。

---

3. 自身の学びの整理としての側面

私自身、アルゴリズムの専門家というわけではなく、学びながら整理している立場 です。

そのため、「算法体系」という言葉を通じて、自分なりにアルゴリズムをどう整理し、理解を深められるかを考えるきっかけにしたい、という意図もあります。

この表現が必ずしも広く受け入れられるかはわかりませんが、少なくともアルゴリズムを体系的に捉える重要性 を共有できればと思っています。

---

補足

本記事は 「アルゴリズム初心者向け」 を想定しており、基礎的なアルゴリズムの理解を深めながら、体系的に学べる視点 を提供したいと考えています。

そのため、「算法体系」という言葉は単なる造語ではなく、アルゴリズムを単体の知識ではなく、より広い視点で捉えるための試み という意図を込めています。

2.アルゴリズムの計算量とは？

アルゴリズムには［計算量］という指標があります。
これは「どれだけの計算が必要か」を数値や文字式で表すもので、アルゴリズムの効率を測る重要な要素です。

細分化した算法体系として捉えると分かりやすいです。

計算量を数字式で表す例

授業の例を使って考えてみましょう。

• アルゴリズムA
  先生Aは、テストの点数をもとに生徒の理解度を判断します。
  • 10問のテストなら、10回の採点が必要
    → 計算量10
  • 各問題に小問が3つあるなら、10×3=30回の採点
    → 計算量30

このように、繰り返しの回数が増えると計算量も増えます。

計算量を文字式で表す例

計算量は文字式で表現できます。
ここでよく使われるのが［$n$］^[1]という変数です。

• アルゴリズムC（小問の数が不明な場合）
  例えば、問題が10問、小問の数を $n$ とすると、
  計算量 = $10×n$
  　　　 = $10n$

このように、文字式で表現することを「一般化」^[2]と呼びます。
文字式を使うと $n$ がいくつでも対応可能になり、アルゴリズムの一般化ができます。

計算量の成り立ち

私たちは普段から、「どの方法が一番早いか、効率がいいか」を考えて行動しています。
計算量の考え方は、これを数学的に整理し、より複雑な問題にも応用できるようにしたものです。

例えば、レジでどの列に並ぶかを考えるとき、人の数だけでなく、一人ひとりの会計の速さも影響します。
計算量は、こうした「処理にかかる時間」を一般化して考えるための方法です。

ここからは、計算量の基本的な考え方を、もう少し詳しく整理してみましょう。

時間計算量と空間計算量の違いを整理する

実は、計算量には 時間計算量 と 空間計算量 の2つがあります。

• 時間計算量：処理にかかる時間（データの比較・交換、関数の呼び出し^[3]）
• 空間計算量：使用するメモリ量（補助空間^[4]、空間の複雑さ^[5]）

授業の例では、この時間計算量について取り上げてきました。
ほとんどの場合、時間計算量のほうが大きい ので、計算量を求めるときは 時間計算量の中で最も大きい要素 に注目します。

計算量の分析方法

アルゴリズムの効率を評価する指標として、計算量を分析することが重要です。
計算量の分析方法には以下の3種類があります。

• 最善計算量（最善分析）^[6]：最も効率的な場合の計算量
• 最悪計算量（最悪分析）：最も時間がかかる場合の計算量
• 平均計算量（平均分析）^[7]：全入力パターンの平均的な計算量

計算量のぶれ幅を調べるために種類の違いを設けています。
これらを求めることで、アルゴリズムの性能を評価できます。

計算量を実際記法（一般式）で表す例^[8]

実際に分析方法に則って3種類の計算量を求めます。
あとで出てくる記法と区別するために、実際記法という名称を付けています。
以下は、文字列検索の力まかせ法を実際記法で表す例です。

• 最善分析の例^[9]
  $T(n) = m$
• 最悪分析の例^[10]
  $T(n) = nm -m^2 + m$
• 平均分析の例
  難解なため、ここでは省略します。

計算量を漸近記法（ランダウ記法）で表す例

分析方法に則って3種類の計算量を求めたら、それらを漸近記法で表します。
漸近記法で求めた計算量のことを 漸近計算量^[11] と呼びます。
漸近記法では、計算量を表す際に入力の大きさ $n$ に対する最も支配的な項だけを考えます。

例えば、$T(n) = n^2 + n + 1$
という計算量がある場合、それぞれの項の増加速度を比較すると

• $n^2$ は二次関数で最も成長が速い
• $n$ は一次関数で、 $n^2$ に比べると影響が小さい
• 定数 $1$ は $n$ が大きくなると無視できる

このため、最も影響の大きい $n^2$ だけを残し、他の項を無視します。
漸近計算量は $O(n^2)$^[12] である
これは、大きな $n$ における計算量の上限を示し、アルゴリズムの効率を把握するのに役立ちます。

実際記法と漸近記法の比較例

実際記法	漸近記法
$n^2+n+1$	$n^2$
$n\log {(n)} +n$	$n \log n$
$2n+1$	$n$
$n+m$	$n+m$[13]

最終的な解答例：「各分析方法の漸近計算量はいくつか？」

• 解答例1:力まかせ法の最悪分析の漸近計算量
  $T(n) = nm -m^2 + m$
  漸近計算量は $O(nm)$ である
• 解答例2^[14]:再帰処理を含む二分探索の最悪分析の漸近計算量
  $T(n)=2\log {(n)} +1$
  漸近計算量は $O(\log n )$ である
• 解答例3^[15]:線形探索を含む基数ソートの最悪分析の漸近計算量
  $T(n)=2nm$
  漸近計算量は $O(nm)$ である

まとめ

計算量を求める目的は、漸近記法を用いて漸近計算量を導き、アルゴリズムの効率を評価することです。

計算量の分析方法には 最善・最悪・平均 の3種類があり、最善の計算量を小さくすることが重要ですが、最悪・平均の計算量もアルゴリズムの性能指標となります。

また、計算量には 時間計算量と空間計算量 があり、通常は時間計算量を考えます。
時間計算量も3種類に細かく分類され、アルゴリズムごとに異なります。

計算量とは、アルゴリズム（=算法体系）を体系的に表現するものであり、アルゴリズムの定義は以下の通りです。

• 基本定義:
  「問題を解決するための手順やルールの集合」
• 体系的定義:
  「ある目的を達成するために必要な情報について何をもとに判断するか？」

---

数学の学び直しで理解を深める
アルゴリズムの理解を深めるためには、数学の基礎が非常に重要です。
https://zenn.dev/algorithm_math/articles/1631216a6976a9

---

脚注

1. 計算量の文字式には、よく $n$ が使われます。
   これは「自然数（natural number）」の略で、$1, 2, 3...$のような正の整数を指します。
   アルゴリズムの計算量では、［変数］として扱われ、問題数やデータの大きさなどを表します。

2. 一般化して出来た文字式を「一般式」と呼びます。
   また、必ずしも文字式にできるとは限りません。
   繰り返さない処理や、あらかじめ計算量が決まっていたり、予測できるような場合には、数値で表現します。
   計算量の表現方法として［数値，数字式，文字式］で区別しています。
   数値は上記のようなもので、数字式は文字式に変換することが出来る形との捉え方です。

3. プログラミングで使われる手法で、ある値を得るために複数の数式をまとめたものです。
   関数を呼び出す際に 引数（数値や文字列）を渡しますが、引数なしの関数も作れます。

4. 処理データを保持する空間

5. 初期データの入出力に使う空間

6. 資源は有限で時間や空間に制約があるため、より速くより小さいものが求められます。

7. ［平均］では、各入力に対する厳密な答えを得られない場合があります。

8. 式の左辺を表す方法は2種類あります。
   $T(n):$ $n$ の関数の計算量
   $T(f(n)):$ $n$ の関数 $f(n)$ の計算量
   一般化には $T(n)$ がよく使われます。
   $「T」$ は「Turing machine, Time, Task」いずれかの頭文字とされます。
   $「f」$ は「関数」の英語訳「function」の頭文字です。

9. これは $n$ に依存しない計算量で、何らかの回数 $m$ が関与するとき、最善計算量を求める際に見られる表記です。
   最善の計算量を求めるときには、右辺が $n$ を除く変数や数値のみとなる場合があります。
   それは、一般化^[2:1]の説明で述べたような理由です。
   文字式に変換するときに $n$ 以外の変数の場合があるということです。
   ただし、左辺の括弧内は計算量を意味する $T(n)$ のまま変更しません。
   最善の計算量を求めるときだけ括弧内を変更すると、一貫性がないからです。

10. この式において $n$ は、左辺の $T(n)$ では関数の引数を示し、右辺の $\log(n)$ では対数の真数を意味します。

11. 「計算量を求める」と言った場合には、この漸近計算量を求めることを最終目的としています。
    なぜなら、アルゴリズムのおおよその計算量目安が分かるからです。

12. 漸近記法の具体的な表記方法は３種類あります。
    $O(f(n)):$ 計算量が $n$ の関数 $f(n)$ の定数倍以内になる
    $Ω(f(n)):$ 計算量が $n$ の関数 $f(n)$ の定数倍以上になる
    $θ(f(n)):$ 計算量が $n$ の関数 $f(n)$ の定数倍になる
    漸近記法というと基本的に$「O」$を使います。
    $「O」$ は［Order of growth］の頭文字です。

13. 漸近記法では変数 $n$ にかかる係数は無視できますが、 $n×m$ のような変数の係数は $n$ と同様に計算量の大きさを左右するため省略できません。

14. 実際記法のように $O(n)=\log n$ といった記述にすると間違いです。
    なぜかというと、実際記法の計算量 $T(n)$ と混同してしまうからです。
    もうひとつには、$n$ か $f(n)$ どちらの定数倍以内なのか混乱するからです。

15. 数学的に言うと係数は変数の前に付くもので、$m$ も $n$ の前に位置付けがちですが、係数順もアルファベット順も無視して $n$ の後ろに配します。
    漸近計算量として、省略できる係数かどうかを区別するためです。
    そのため、実際記法においても、あらかじめ係数を区別して前後に配します。