O記法は、コンピュータサイエンスにおいてアルゴリズムの複雑さを表すために使用される。 優秀なアルゴリズムは高速に結果を返し、かつ複雑度は低いと言える。
アルゴリズムは常に同じ結果にはならず、与えられるデータによって異なる結果になる場合がある。同じ要素を扱った場合でも、あるケースでは高速に実行され、他のケースでは低速になるということが起きる。
以下にJavaScriptでの例を示す。例中の基本時間は1msとする。
O(1)
arr[arr.length - 1]
定数時間。1000 elements = 1ms.
arrayの要素数にかかわらず、理論的には同じ毎回時間実行することになる。(データ量に依存せず毎回1msの処理時間)
O(N)
arr.filter(fn)
線形時間。1000 elements = 1000ms.
実行時間はarrayの要素数に比例して線形的に増加する。 これは、関数が結果を返すまでに全てのarrayの要素をループするからである。
O([1, N])
arr.some(fn)
1000 elements = 1ms <= x <= 1000ms.
実行時間は与えられるデータによって異なる。ここでの最良の場合はO(1)であり、最悪の場合はO(N)である。
O(logN)
arr.sort(fn)
対数時間。1000 elements = 3ms.
ブラウザは通常、logNであるsort()メソッドのクイックソートアルゴリズムを実装している。これは大規模な要素に非常に効率的。
O(N2)
for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { // ... } }
二乗時間。1000 elements = 1000000ms.
実行時間は要素の数に応じてその二乗で増えていく。ネストされた二重ループなどはこれにあたる。
O(N!)
const permutations = arr => { if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr return arr.reduce( (acc, item, i) => acc.concat( permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map(val => [ item, ...val ]) ), [] ) }
階乗時間。1000 elements = Infinity (practically) ms.
Nの階乗で実行時間は増加するため、1つの要素を追加するだけでも実行時間の増加に大きく影響する。
tips
- ネストされたループの実行時間は指数関数的に増加するので、そのようなコードを書く際には計算量に注意。
