壊れた計算機

CLRS 1

CLRS

An Introduction to Algorithms

Exercise 1.1-1

sort : 山ほどある。検索結果の表示とか、最大値を調べるときとか。
convex hull : 監視カメラとかアンテナとか壁とか設置するとき

Exercise 1.1-2

空間・表示方法・アルゴリズムの再利用のしやすさ。

Exercise 1.1-3

リスト：先頭へのアクセスは速いが、任意の要素へのアクセスは遅い

Exercise 1.1-4

どちらも最短距離をもとめる。
セールスマン問題は全ての点を巡回するという制約がある。計算量のクラスが違うかも。

Exercise 1.1-5

最適解のみ：trueかfalseか判定する問題に多い、また重要な所で使われるアルゴリズムとか。（でも確率的素数とかあるんだよな）
近似解で十分：連続的な値をOutputする問題に多い、乗り換え経路を求めるアルゴリズムなど。

Exercise 1.2-1

amazonの自動でセールをする機能 : 倉庫の容量と値段を秤にかける。
検索 : suffix arrayを作っておいたりする
ダイヤの作成
原発の制御

Exercise 1.2-2

nが8〜9以下の時

Exercise 1.2-3

n=15

Problem 1-1

f	second	century
$\log_2 n$	$2^{10^6}$	$2^{10^{16}}$
$n$	$10^6$	$10^{16}$
$n \log_2 n$	$10^5$	$10^{15}$
$2^n$	$18$	$48$
$n!$	$11$	$17$
$n^n$	$7$	$14$