【基本情報・応用情報】アルゴリズムだああああ！種類・計算量・動き

はじめに

基本情報や応用情報でのアルゴリズムを一気に復習できるような記事です！

データ構造やプログラミングの基礎知識については記述していないので，事前に学んでおいてください．

探索アルゴリズム

	特徴	平均計算量	補足
線形探索	先頭から順に探索	$O(n)$	ソート不要
2分探索	中央値と比較し範囲を半減	$O(\log n)$	ソート必要
ハッシュ探索	キーをハッシュ関数で変換	$O(1)$	衝突対策が必要

整列アルゴリズム

	特徴	平均計算量	安定
選択法	最小値を選んで順に並べる	$O(n^{2})$	X
バブルソート	隣接要素を比較・交換	$O(n^{2})$	◯
挿入法	要素を適切な位置に挿入	$O(n^{2})$	◯
シェルソート	挿入法の改良版，一定間隔をあけて行う	$O(n^{1.2})$~$O(n^{1.5})$ ※	X
クイックソート	分割統治法、ピボットで分割	$O(n\log n)$	X
ヒープソート	ヒープ構造を利用	$O(n\log n)$	X
マージソート	分割統治法、部分列を比較してマージ	$O(n\log n)$	◯

※シェルソートの最低時の計算量は$O(n^{2})$

選択ソート

バブルソート

挿入ソート

画像

シェルソート

クイックソート

ヒープソート

マージソート

基本情報・応用情報記事