一般的なアルゴリズムの時間複雑度
5425 ワード
常用アルゴリズムの時間の複雑さはよく分かりませんので、インターネットで関連資料を探して、他の人の資料をコピーして、自分で勉強します.
検索
アルゴリズム
データ構造
時間の複雑さ
空間複雑度
平均
最悪
最悪
深さ優先検索(DFS)
Graph of|V𞓜vertices and|E edges
Graph of|V𞓜vertices and|E edges
Sorted array of n elemens
Aray
Graph with|V vertices and𞓜E edges
Graph with|V vertices and𞓜E edges
Graph with|V vertices and𞓜E edges
アルゴリズム
データ構造
時間の複雑さ
最悪の場合の補助空間の複雑度
最適
平均
最悪
最悪
クイックソート
行列
行列
行列
行列
行列
行列
行列
行列
データ構造
時間の複雑さ
空間複雑度
平均
最悪
最悪
索引
検索
挿入
削除
索引
検索
挿入
削除
基本配列
Heapps
時間の複雑さ
山をつくる
最大値を検索
最大値を抽出
Increase Key
挿入
削除
統合
チェーンシート(並べ替え済み)
ノード/サイド管理
Strage
Add Vetex
Add Edge
Remove Vetex
Remove Edge
Query
隣接表
検索
アルゴリズム
データ構造
時間の複雑さ
空間複雑度
平均
最悪
最悪
深さ優先検索(DFS)
Graph of|V𞓜vertices and|E edges
-O(|E| + |V|)O(|V|)広さ優先検索(BFS)Graph of|V𞓜vertices and|E edges
-O(|E| + |V|)O(|V|)二分割検索Sorted array of n elemens
O(log(n))O(log(n))O(1)ざっと調べるAray
O(n)O(n)O(1)最短経路-Dijkstraは、小根山を優先列としています.Graph with|V vertices and𞓜E edges
O((|V| + |E|) log |V|)O((|V| + |E|) log |V|)O(|V|)最短経路-Dijkstraは、無秩序配列を優先列とする.Graph with|V vertices and𞓜E edges
O(|V|^2)O(|V|^2)O(|V|)最短経路-Bellman-FordGraph with|V vertices and𞓜E edges
O(|V||E|)O(|V||E|)O(|V|)並べ替えアルゴリズム
データ構造
時間の複雑さ
最悪の場合の補助空間の複雑度
最適
平均
最悪
最悪
クイックソート
行列
O(n log(n))O(n log(n))O(n^2)O(n)並べ替え行列
O(n log(n))O(n log(n))O(n log(n))O(n)積み上げ順序行列
O(n log(n))O(n log(n))O(n log(n))O(1)泡の並べ替え行列
O(n)O(n^2)O(n^2)O(1)並べ替えの挿入行列
O(n)O(n^2)O(n^2)O(1)並べ替えを選択行列
O(n^2)O(n^2)O(n^2)O(1)バケツの並べ替え行列
O(n+k)O(n+k)O(n^2)O(nk)ベースの並べ替え行列
O(nk)O(nk)O(nk)O(n+k)データ構造データ構造
時間の複雑さ
空間複雑度
平均
最悪
最悪
索引
検索
挿入
削除
索引
検索
挿入
削除
基本配列
O(1)O(n)--O(1)O(n)--O(n)ダイナミック配列O(1)O(n)O(n)O(n)O(1)O(n)O(n)O(n)O(n)チェーン?テーブルO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)二重リンク計O(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)時計を跳ぶO(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n log(n))ハッシュ・テーブル-O(1)O(1)O(1)-O(n)O(n)O(n)O(n)ツリー検索O(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n)デカルトの木-O(log(n))O(log(n))O(log(n))-O(n)O(n)O(n)O(n)B-ツリーO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)赤黒い木O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)木を伸ばす-O(log(n))O(log(n))O(log(n))-O(log(n))O(log(n))O(log(n))O(n)AVLの木O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)積み重ねるHeapps
時間の複雑さ
山をつくる
最大値を検索
最大値を抽出
Increase Key
挿入
削除
統合
チェーンシート(並べ替え済み)
-O(1)O(1)O(n)O(n)O(1)O(m+n)チェーンテーブル(並べ替えなし)-O(n)O(n)O(1)O(1)O(1)O(1)二叉の山O(n)O(1)O(log(n))O(log(n))O(log(n))O(log(n))O(m+n)二つの山-O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))フィボナッチの山-O(1)O(log(n))*O(1)*O(1)O(log(n))*O(1)図ノード/サイド管理
Strage
Add Vetex
Add Edge
Remove Vetex
Remove Edge
Query
隣接表
O(|V|+|E|)O(1)O(1)O(|V| + |E|)O(|E|)O(|V|)関連表O(|V|+|E|)O(1)O(1)O(|E|)O(|E|)O(|E|)隣接行列O(|V|^2)O(|V|^2)O(1)O(|V|^2)O(1)O(1)関連行列O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|E|)