学習アルゴリズム

第2章. アルゴリズムを分析する

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

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

• ビッグ・オー表記法を用いてアルゴリズムの性能を分類する（時間またはストレージ）。

• いくつかのパフォーマンスクラスがある：

  • O(1) または一定

  • O( N)またはlog 対数

  • O(N)または線形

  • O(N N)log ¹

  • O(^N2)または2次式

• 漸近解析は、アルゴリズムがサイズNの問題インスタンスを処理するのに必要な時間（または記憶領域）を、Nの観点からどのように推定するか。

• 値が昇順、ソート順で表示される配列の扱い方。

• ソートされた配列内の値を検索するバイナリ配列検索アルゴリズム。

この章では、アルゴリズムの性能をコンピューティング性能とリソース使用量の観点からモデリングする際に、理論家と実務家が同様に使用する用語と表記法を紹介する。 ソフトウェアプログラムのランタイム・パフォーマンスを評価するとき、あなたは完全に満足するかもしれない。しかし、ランタイム・パフォーマンスを改善したい場合、本書はプログラムのデータ構造とアルゴリズムから始めるべきことを示す。あなたはいくつかの具体的な疑問に直面することになる：

私は特定の問題を最も効率的な方法で解決しているだろうか？

パフォーマンスを大幅に向上させる他のアルゴリズムがあるかもしれない。

私は最も効率的な方法でアルゴリズムを実装しているだろうか？

排除できるパフォーマンス・コストが隠れている可能性もある。

もっと速いコンピューターを買うべきか？

まったく同じプログラミングでも、実行するコンピュータによって実行時の性能は異なる。この章では、コンピュータ科学者が、ハードウェアの定期的な改良を考慮した解析テクニックをどのように開発したかを説明する。

まず、問題インスタンス・サイズが増加し続ける場合のプログラミングの実行時性能をモデル化する方法を示す。小さな問題インスタンス・サイズに対するアルゴリズムの実行時性能は、問題インスタンス内の実際の値やコンピュータ・タイマーの分解能に敏感である可能性があるため、正確に測定するのが難しい場合がある。 プログラムが十分に大きな問題インスタンスを処理するようになれば、経験的モデルを用いて実行時の振る舞いを分類するモデルを開発することができる。

経験モデルを用いてパフォーマンスを予測する

理論的な分析が実際のソフトウェアシステムでいかに実用的であるかを示す例から始めたい。タスクは真夜中に開始され、午前6時までに完了しなければならない。データセットには数百万の値が含まれ、今後5年間でサイズが倍増すると予想されている。

表2-1は、これらのデータセットにおけるプロトタイプのランタイム・パフォーマンスである。

表2-1. プロトタイプのランタイム性能

N	時間（秒）
100	0.063
1,000	0.565
10,000	5.946

これらの予備的な結果は、100,000や1,000,000といったより大きな問題インスタンスに対するプロトタイプの性能を予測できるだろうか？このデータだけから数学モデルを構築して、与えられた問題インスタンス・サイズの実行時性能を予測する関数T(N)を定義してみよう。正確なモデルは、表2-1の3つの値に近いT(N)を計算するだけでなく、表2-2（括弧内にこれらの3つの時間結果を繰り返す）に示すように、Nのより高い値を予測する。 ...