アルゴリズム×数学の学び直しPublicationへの投稿
⚙️

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

zoldof
に公開
プログラミング
AtCoder
学習
アルゴリズム
記事投稿コンテスト「今年の最も大きなチャレンジ」
tech

参考サイト

はじめに

この記事の大まかな内容

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

この記事の背景

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

この記事が役立つ人

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

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

ことばの語源

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

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

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

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

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

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

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

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

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

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

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

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

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

アルゴリズムを学ぶと、

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

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

アルゴリズムを学ぶ意味とは？〜人工知能（AI）時代における知の広がり〜

アルゴリズムを学ぶことは、単なるプログラミングスキルの向上にとどまりません。
私たちの思考力を深め、問題解決のための型を身につけることができるからです。
例えば、 2つの時刻差を求めるアルゴリズム のような具体的な問題を通して、どのように思考を整理し、効率的に解決策を見つけるかを学ぶことができます。

こうした具体的な課題から出発し、思考の射程をどんどん広げていくことは、アルゴリズム学習の楽しさのひとつです。
問題解決のためにどんな枠組みを使い、どのように効率的に解決するかを考えることで、視野が広がり、新たな発見が得られます。

しかし、近年では人工知能の発展によって、こうした下層の技術的な部分（実装や全体構造）がすべて人工知能によって代替されるのではないか、という声も聞かれるようになっています。

確かに、現時点でも［ChatGPT］や［GitHub Copilot］のような人工知能は、関数レベルのコード生成を日常的にこなしており、設計レベルの提案や構造的な補助も行えるようになっています。

ただし、完全に 関数群を自動生成し、永続的に保守する人工知能 というものは、まだ登場していません。
現在の人工知能は、必要な関数群をその場で作り出す即席段階にあります。

そのため、人工知能を使いこなすためには、どのような意図を持ち、どのような出力を期待しているのかを人間側が明確に伝える必要があります。
つまり、「何をやりたいのか」を［言語化，論理化］する力が、これまで以上に重要になってきます。

そこで役立つのが、アルゴリズムの知識です。

アルゴリズムを学ぶことで、人工知能に対して

  • どのような思考手順を辿ってほしいか
  • どういう選択肢があって、どれを優先するか

といった指示の粒度を操作できるようになります。

それぞれのアルゴリズムは、小さな知識のかけらにすぎません。
しかし、それらがつながることで、世界の見え方そのものが変わります。

なぜなら、アルゴリズムは単なる技術ではなく、「どの思考をどのように変更し、世界観を広げていくか」という知的活動そのものだからです。

今後、人工知能はますます賢くなり、最終的には解決指針の提示までも担うようになるでしょう。
それは、次のいずれかの形をとると考えられます：

  • 形式的な指針提示： 人間が設定した価値観や目的を、膨大な情報から演繹的に最適化して導き出す
  • 自己意識を持った指針生成： 人工知能がある種の意識や意志を持ち、自らの世界観に基づいて解決指針を提示する

それでも、なぜアルゴリズムを学ぶのか？

もちろん、アルゴリズムを学ぶ理由は「趣味で好きだから」でも全然問題ありません。
それでも、これからの時代における実用性は十分にあります。

例えば、人工知能に指示を出す際、最も重要なのは 「どんな思考を、どう変形して目的にたどり着かせたいか」 という問いです。

アルゴリズムは、その 思考の骨組み を与えてくれます。
だから、自分の中にいくつかのアルゴリズム的発想を持っていると、

  • 人工知能に対して、より的確な指示が出せる
  • 人工知能の出力を［検証，調整］する目を持てる
  • 必要に応じて新しい構造を［発明，適用］できる

といった形で、人工知能を 共創の相手 として扱えるようになります。

アルゴリズムというのは、それ単体で完結するものではありません。
シンプルな手順の中に、いくつもの分野に通用する応用性や、相互作用による新しい発見が詰まっています。

世界観をどう広げていくか？

だからこそ、アルゴリズムを学ぶ意味は、単にプログラミングスキルを身につけることではありません。

どの思考を、どのように変更し、どんな世界観を広げていくか？

この問いを自分の中に持てるようになる。
それを支えてくれるのが、アルゴリズムです。

人工知能がどれだけ進化しても、私たちの 問い は残ります。
そして、その問いに、より深く、柔らかく、面白く向き合うために、アルゴリズムは今後も学ぶ価値があるのです。

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

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

先生による授業の決め方

  • アルゴリズム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]、空間の複雑さ[6]）

最近では、技術の進歩によってスマホやパソコンのメモリ容量もかなり大きくなっています。
そのため、アルゴリズムが使う空間計算量（メモリ使用量）は、相対的に見るとそれほど大きくありません。
こういった背景から、計算量を評価する際には、時間計算量の中で最も大きい要素に注目します。

計算量の分析方法

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

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

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

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

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

  • 最善分析の例[11]
    T(n) = m
  • 最悪分析の例[12]
    T(n) = nm -m^2 + m
  • 平均分析の例[13]
    T(n) \approx \frac{1}{2}[(nm - m^2 + m) + n]

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

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

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

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

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

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

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

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

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

まとめ

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

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

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

計算量とは、アルゴリズム（=算法体系）を細分化したものであり、アルゴリズムの定義は以下の通りです。

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

数学の学び直しで理解を深める

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

脚注

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

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

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

  4. RAM（Random Access Memory）は、スマートフォンやコンピューターが一時的にデータを保存し、処理を行うための領域です。アプリの起動や動作、マルチタスクの処理などに使用されます。 ↩︎

  5. 処理データを保持する空間 ↩︎

  6. 初期データの入出力に使う空間 ↩︎

  7. プログラムを実行したときに結果が反映されるまでの時間です。
    スマホやパソコン、またはアプリを動かすのにプログラムが使われています。
    プログラムを作るにはプログラミングが必要です。 ↩︎

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

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

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

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

  12. この式において n は、左辺の T(n) では関数の引数を示します。
    例えば右辺が \log(n) の場合には、関数の引数ではなく対数の真数を意味します。
    括弧が意味する内容に注意が必要です。
    実際記法の場合、対数の真数への定数追加を想定して括弧を付けます。 ↩︎

  13. 実際記法の計算量に近似式を用いる場合があります。 ↩︎

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

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

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

  17. 再帰だと「等しいか？」「大きいか小さいか？」の2段階判定を毎回やるので2倍。
    また、実際記法のように O(n)=\log n といった記述にすると間違いです。
    なぜかというと、実際記法の計算量 T(n) と混同してしまうからです。
    もうひとつには、n か f(n) どちらの定数倍以内なのか混乱するからです。 ↩︎

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

アルゴリズム×数学の学び直し
アルゴリズム×数学の学び直しPublication

このパブリケーションでは、アルゴリズムの理解を深めるために必要な数学を基礎から学び直します。算数・数学の基本概念から始め、実践的なアルゴリズムの活用までを丁寧に解説。初心者から学び直したい方、プログラミングやデータ構造に興味がある方に向けた内容をお届けします。

Discussion