アルゴリズムデザイン読書メモ2-1

アルゴリズムデザインを読んでるのですが、
先週に引き続き読書メモがあるので、それを貼っておきます。

アルゴリズムデザイン: Jon Kleinberg, Eva Tardos

以下、メモ。

■第2章：アルゴリズム解析の基礎事項
- 概念の本質の具体化手法
- 入力データと計算量の関係を見積もる数学的枠組み
- 基本的なアルゴリズムの計算上界
-- GSアルゴリズムの実装
-- 多くの異なる計算時間を概観
-- アルゴリズムの特徴を整理、分類する。
- 有用なデータ構造例
-- 優先度付きキュー
-- ヒープ

●クイックソートとヒープソート
どっちの方がより良いかな。。

■計算容易性
本書の目的 = 計算問題に対する効率の良いアルゴリズムの発見

本書特有のアプローチ
１、設計原理を特定し、きちんと記述する
- 基本的な事項から取り上げつつ、冗長でないように

２、取り上げる問題の多くが離散的な性質を持つ
- 目標：可能な組み合わせの巨大空間から、指定された条件を満たす解を効率よく発見

３、計算時間(running time)と、領域量(space)に着目する。
- より速く、より小さく

■効率性の定義

欲しい定義
１、実行環境や入力インスタンスに依存しない
- 単に「速さ」に着目するなら、計算機の進歩を待てば良い
２、入力サイズが増加した時の値が予測できる
- 入力サイズが巨大になったときも効率を予測できるかどうか

学んだこと
- where : どこで？
- how well : どのようにうまく？


■最悪の場合の計算時間と全探索

最悪の場合の解析(worst-case analysis)
- アルゴリズムの実際の効率を捉えるのに適当

平均の場合の解析(average-case analysis)
- しばしば泥沼にはまる
-- ランダムな入力インスタンスの出現範囲を表現するのは困難
-- ランダムな入力をどのように生成するべきか。。。

⇒本書では、計算時間について最悪の場合の解析を考える

安定マッチング問題
単純には「n × nの組み合わせについて、すべての完全マッチングを列挙し、それぞれが安定かを調べる必要があった」
⇒探索空間(search space)が巨大であった

好意順リストの概念を取り入れたら！？
⇒高々「長さnの2n個のリストの量」= 2n^2という入力サイズに、まぁぁ比例する計算量
⇒全探索(brute-force search)しなくて済んだ

注目！
- この「入力サイズNに比例する」という結論を解析レベル(analysis level)で得た

本書では、つまりは全探索より本質的に良い手法を考えたい

学んだこと
- 本質的に良い性能とは何か
⇒もっと注意深く考察し、計算時間の数量化を試みよう

■効率性の定義としての多項式時間
自然な組み合わせ問題の計算量
- 入力サイズNの指数関数で増加する傾向

⇒入力サイズNの定数C倍だけ増加する傾向のアルゴリズムが欲しい

★多項式の計算時間(polynomial running time)
以下の条件を満たすような計算時間
- 定数 : c > 0, d > 0
- すべての入力インスタンスのサイズ : N
- 計算時間 : cN^d個の計算ステップで押さえられる

このような計算時間をもつアルゴリズムを
多項式時間アルゴリズム(polynomial-time algorithm)という。

- 計算時間 : cN^dのときに入力データサイズが4Nになったら？
⇒c(2N)^d = c(2^d * N^d)
このとき、c*2^dは定数だから結局データサイズに、まぁあ比例してるといえる。

表2.1 = 入力インスタンスのサイズに対する計算時間

学んだこと
- それぞれの問題は固有のレベルの計算容易性を持つ
- 効率的な解は、ある時とない時がある

■増加の漸近的オーダー
最悪の計算時間を考える時に、あんまり細かく計算時間を計算する意味は無い。
- 例、ステップ数で計算時間を算出
⇒高水準言語で見積もって、低水準言語で実行すると、ステップ数が変わる

Ｏ：漸近的上界(asymptonic upper bound)
- 計算時間T(n)がＯ(f(n))

Ω：漸近的下界(asymptonic lower bound)
- 計算時間T(n)がΩ(f(n))

Θ：漸近的にタイトな限界(asymptonic tight bound)
- 計算時間T(n)がＯ(f(n))かつΩ(f(n))

以下つづく

今後も気が向いたら公開する予定。