なっとく！アルゴリズム
タイトル
なっとく！アルゴリズム
著者
年
2017
リソース
概要
基本的なalgorithmの説明
図が超豊富
例はPythonで書かれている
内容
第一章
入力：ソートされたリスト
循環セールスマン問題はO(n!)（とてもおそい）
p.71
ソート
ループと再起
ループでかければ再起でかける
再帰を使うと再起が終わるまで未処理の情報を確保したスタックを持ち続ける必要があるのでメモリを食う
末尾再帰だとこの問題は起きないが、本書のカバー範囲よりは高度なので割愛されていた
たくさん再起してメモリがなくなるとStack overflowになる
なぜ再帰を使うのかという説明は「関数型言語で使うから」だった。いまいち腹落ちしない
分割統治法という問題の考え方
分割倒置法を用いたソートクイックソート
単純に先頭をpivotとした場合で基本ケースに帰着できることを帰納法で証明
かなりわかりやすい
レコメンドシステム