Big O Notation

アルゴリズムの実行時間を入力サイズに対して表す方法。 数種類しかないので、覚えるのは簡単。

• O(1): 定数時間。入力サイズに関係なく一定の時間で実行される。
• O(log n): 対数時間。入力サイズが増えるにつれて、実行時間が対数的に増加する。また実用的には O(1) と同じくらい無視できるスケールである。
• O(√n): 平方根時間。入力サイズの平方根に比例して実行時間が増加する。
• O(n): 線形時間。入力サイズに比例して実行時間が増加する。
• O(n log n): 線形対数時間。入力サイズに比例して、さらに対数的な増加がある。
• O(n^2): 二次時間。入力サイズの二乗に比例して実行時間が増加する。
• O(n!): 階乗時間。入力サイズの階乗に比例して実行時間が増加する。

Space Complexity

アルゴリズムが使用するメモリの量。
一般に実行時間とは負の相関関係にある。チューリング理論と関連が深いのでそちらを参照。
利用できるリソースにより評価するとよい。