学習アルゴリズム

第1章. 問題解決

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

この章では、次のことを学ぶ：

• 入門問題を解く複数のアルゴリズム。

• サイズNの問題インスタンスに対するアルゴリズムの性能をどのように考えるか。

• 与えられた問題インスタンスを解くときに、キー演算子が呼び出される回数をカウントする方法。

• 問題インスタンスのサイズが2倍になったときの成長順序を決定する方法。

• サイズNの問題インスタンスに対してアルゴリズムが実行するキー演算の数をカウントすることによって、時間の複雑さを見積もる方法。

• サイズNの問題インスタンスに対してアルゴリズムが必要とするメモリ量を決定することにより、問題領域の複雑さを見積もる方法。

始めよう！

アルゴリズムとは何か？

アルゴリズムがどのように機能するかを説明することは、物語を語るようなものだ。各アルゴリズムは、通常の解決策を改善する斬新な概念やイノベーションを導入している。この章では、アルゴリズムの性能に影響を与える要因を説明するために、単純な問題に対するいくつかの解を探索する。その過程で、実装に依存しないアルゴリズムのパフォーマンスを分析するためのテクニックを紹介するが、実際の実装から得られた経験的証拠も必ず提供する。

注

アルゴリズムとは、コンピュータプログラムとして実装され、予測可能な時間で正しい結果を返す、段階的な問題解決メソッドのことである。アルゴリズムの研究は、正しさ（このアルゴリズムはすべての入力に対して機能するか）と性能（これはこの問題を解く最も効率的な方法か）の両方に関係する。

これが実際にどのようなものか、問題解決メソッドの例を見てみよう。順序なしリストの中で最大の値を発見したいとしたらどうなるだろうか？図1-1の各Pythonリストは問題インスタンスであり、アルゴリズム（円柱で示される）によって処理される入力である。 このアルゴリズムはどのように実装されているか？異なる問題インスタンスに対してどのように実行するか？ 100万個の値のリストから最大の値を発見するのに必要な時間を予測できるか？

図1-1. アルゴリズムによって処理される3つの異なる問題インスタンス

アルゴリズムは単なる問題解決手法ではない。プログラムは予測可能な時間で完了する必要もある。Pythonの組み込み関数max() はすでにこの問題を解決している。さて、ランダムなデータを含む問題インスタンスに対するアルゴリズムの性能を予測するのは難しいかもしれないので、注意深く構築された問題インスタンスを特定する価値がある。

表1-1はサイズNの2種類の問題インスタンスに対するタイミングmax() の結果を示している：リストが昇順整数を含むものと、リストが降順整数を含むものである。 あなたの実行は表とは異なる結果をもたらすかもしれないが，あなたの計算機システムの構成に基づけば，以下の2つの文の検証は可能である．

• max() のタイミングは、Nが十分に大きくなると、昇順の方が降順よりも常に遅くなる。

• その後の行でNが10倍になるにつれて、max() 、有効期間も10倍になる。

この問題では最大値が戻り、入力は変更されない。場合によっては、アルゴリズムは新しい値を計算する代わりに、問題インスタンスを直接更新する-例えば、 ...