【読書】「なっとく！アルゴリズム」メモ

Twitterで見かけて読んでみた。本当はだいぶ前に買ったけど文字が小さすぎたのでKindleで再チャレンジしたら読みやすかった

ビッグオー記法について

配列、リンクリストについて

再帰について。ここは妙な苦手意識があったけど、浮かんだ疑問についてのカバーがしっかりしていて理解しやすかった。末尾再帰は知らなかったので理解しておきたいし、Haskellも触ってみたくなった。

クイックソートと分割統治について。クイックソートは知っていたけど、分割統治といいう方法論だとは知らなかったので、一段深く理解できるようになった気がする。

ハッシュについて。ハッシュが衝突した際にリンクリストになるというところは納得感がすごかった。今触っている言語でどう実装されているか気になったので調べよう。

幅優先探索について。感覚で触ってしまっていた箇所なので、言葉で読めたのは良かった。

ダイクストラ法について。理解できたけどそれ以上はよくわからなかった。ベルマンフォード法も調べてみよう。

貪欲法、NP完全問題について。これは全く知らなかった内容で、近似で妥協するという点は目からウロコだった。

動的計画法について。これも理解はできたけど、、という状況。

ｋ近傍法について。内容は単純だったが機械学習にも触れられていて面白かった。

読み始めたきっかけはここに載っているアルゴリズムを理解できるようになるためだったので、挑戦していきたい。（木（ツリー）、転置インデックス、フーリエ変換、並列アルゴリズム、MapReduce、ブルームフィルタとHyperLogLog、SHAアルゴリズム、ディフィー・ヘルマン鍵交換、線形計画法）