16
23

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

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

Last updated at Posted at 2024-10-14

はじめに

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

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

探索アルゴリズム

特徴 平均計算量 補足
線形探索 先頭から順に探索 $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})$

選択ソート

バブルソート

挿入ソート

画像

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

シェルソート

クイックソート

image.png
image.png
image.png
image.png
image.png

ヒープソート

image.png
image.png
image.png
image.png
image.png

マージソート

image.png
image.png
image.png

基本情報・応用情報記事

16
23
7

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16
23

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?