アルゴリズムの計算量を考える時、主なオーダーのグラフは以下のようになります。
\( O(1) \) 定数 Constant、\( O ( \log n) \) 対数 Logarithmic、\( O (n) \) 線形 Linear、\( O ( n /times log n) \) 準線形 Linearithmic 、\( O (n^k), \exists k \gt 1 \) 多項式 Polynomial、\( O (c^n) \) 指数 Exponential、\( O (n !) \) 階乗 Factorial とそれぞれ呼ばれます。
準線形 Linearithmic かそれより速いアルゴリズムであれば実用性があり、より遅い場合は時間がかかりすぎて実用性がないと考えれば、基本的には良いようです。
\( O(1) \) 定数 Constant
ハッシュテーブルの検索や追加
ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
\( O ( \log n) \) 対数 Logarithmic
2分探索
二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
\( O (n) \) 線形 Linear
線形探索
線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
線形探索は最初から最後まで探索を行いますが、2分探索では探索範囲を半分ずつに絞っていくことで、計算量が減少します。
\( O ( n /log n) \) 準線形 Linearithmic
マージソート
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ヒープソート
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
クイックソート
クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
\( O (n^k), \exists k \gt 1 \) 多項式 Polynomial
バブルソート
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう[1]。（単に交換法と言う場合もある）
出典: フリー百科事典『ウィキペディア（Wikipedia）』
挿入ソート
挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである
出典: フリー百科事典『ウィキペディア（Wikipedia）』
\( O (c^n) \) 指数 Exponential
ハノイの塔
ハノイの塔（ハノイのとう、Tower of Hanoi）はパズルの一種。 バラモンの塔または ルーカスタワー(Lucas’ Tower)[注 1]とも呼ばれる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
フィボナッチ数列
上記例1のプログラムでは n が与えられてから Fn が求まるまでに指数時間の計算となるため、実用的ではない。したがって通常は、線形時間で計算するためにメモ化などの手法を用いる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
動的計画法を用いた巡回セールスマン問題
The Held–Karp algorithm, also called Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman[1] and by Held and Karp[2] to solve the Traveling Salesman Problem (TSP). TSP is an extension of the Hamiltonian circuit problem.
From Wikipedia, the free encyclopedia
\( O (n !) \) 階乗 Factorial
巡回セールスマン問題
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
