アルゴリズム問題の、ごく簡単なまとめ
応用情報の対策として1章も終わりに近づいてきました。
今日勉強した内容はプログラム言語とアルゴリズム。
割と体系的に量を覚えなければならないアルゴリズムの方を箇条書き程度にまとめときます。
整列アルゴリズム
ソートのアルゴリズムと計算量をざっと書き出すとこんな感じ。
- 選択ソート：O(n^2)
- バブルソート：O(n^2)
- シェルソート：O(n^2/3)以下
- クイックソート：平均O(nlog(n))、最大O(n^2)
- ヒープソート：O(nlog(n))
- マージソート：O(nlog(n))
- 挿入ソート：O(n^2)
探索アルゴリズム
探索のアルゴリズムも同様に
- 線形探索：O(n)
- 2分探索：O(log(n))
- ハッシュ探索：O(1)
だいたいこんなかんじでしょうか。
ちなみにlogの底はすべて２です。
そもそも、これは記憶モノではなくそれぞれのアルゴリズムの構造を意識すれば自ずから答えが導けるみたいですが、それは別の機会に。
というのも、この間衝動買いしてしまったデータ構造とアルゴリズムの本があるから！
- 作者: Narasimha Karumanchi,黒川利明,木下哲也
- 出版社/メーカー: オライリージャパン
- 発売日: 2013/08/24
- メディア: 大型本
- この商品を含むブログ (6件) を見る
詳しいことはこっちで勉強しようかなって。
なので、それぞれをまたまとめていきたいと思います。（できればコード付きで）
そんなわけで、とりあえず第一章は終わりました。
この参考書は全13章で、そのうち11章が講義部分だから（残りは過去問）わりといいペースな気もします。
ちなみに本番は10月20日。
過去問練習の時間とかを考えたら丁度いいくらいになりそうです。
よしよし。
