Big O notation is used in Computer Science to describe the time complexity of an algorithm. The best algorithms will execute the fastest and have the simplest complexity.
Algorithms don’t always perform the same and may vary based on the data they are supplied. While in some cases they will execute quickly, in other cases they will execute slowly, even with the same number of elements to deal with.
In these examples, the base time is 1 element = 1ms.
O(1)
arr[arr.length - 1]- 1000 elements =
1ms
Constant time complexity. No matter how many elements the array has, it will theoretically take (excluding real-world variation) the same amount of time to execute.
O(N)
arr.filter(fn)- 1000 elements =
1000ms
Linear time complexity. The execution time will increase linearly with the number of elements the array has. If the array has 1000 elements and the function takes 1ms to execute, 7000 elements will take 7ms to execute. This is because the function must iterate through all elements of the array before returning a result.
O(1, N)
arr.some(fn)- 1000 elements =
1ms <= x <= 1000ms
The execution time varies depending on the data supplied to the function, it may return very early or very late. The best case here is O(1) and the worst case is O(N).
O(NlogN)
arr.sort(fn)- 1000 elements ~=
10000ms
Browsers usually implement the quicksort algorithm for the sort() method and the average time complexity of quicksort is O(NlogN). This is very efficient for large collections.
O(N²)
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
// ...
}
}- 1000 elements =
1000000ms
The execution time rises quadratically with the number of elements. Usually the result of nesting loops.
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
The execution time rises extremely fast with even just 1 addition to the array.
Be wary of nesting loops as execution time increases exponentially.
빅 오 표기법이란 무엇인가?
빅 오 표기법은 컴퓨터 과학에서 알고리즘의 시간 복잡도를 설명하는 데 사용된다. 최상의 알고리즘은 가장 빠르게 실행되며 가장 간단한 복잡도를 가질 것이다.
알고리즘은 항상 동일하게 수행되지는 않으며 공급된 데이터에 따라 다를 수 있다. 동일한 요소 수를 다루더라도 경우에 따라서 빠르게 실행될 수도 있고, 느리게 실행될 수도 있다.
이 예시에서 기준 시간은 1 요소(element) = 1ms 이다.
O(1)
arr[arr.length - 1]- 1000 elements =
1ms
상수 시간 복잡도. 배열이 요소 수에 관계없이 이론적으로 (실제 세계의 변동을 제외하고) 실행에 걸리는 시간은 동일하다 .
O(N)
arr.filter(fn)- 1000 elements =
1000ms
선형 시간 복잡도. 실행 시간은 배열이 가진 요소 수와 선형적으로 증가한다. 배열이 1000 요소를 가지고 함수가 1ms 걸린다면, 7000 요소는 7ms가 걸린다. 그 이유는 함수가 결과를 반환하기 전에 배열의 모든 요소를 반복해야 하기 때문이다.
O(1, N)
arr.some(fn)- 1000 elements =
1ms <= x <= 1000ms
실행 시간은 함수에 제공된 데이터에 따라 변동하며, 아주 빨리 반환될 수도 있고 아주 늦게 반환될 수도 있다. 여기서 최상의 경우는 O(1)이고 최악의 경우는 O(N)이다.
O(NlogN)
arr.sort(fn)- 1000 elements ~=
10000ms
일반적으로 브라우저는 sort() 메서드에 대해 quicksort 알고리즘을 구현하며 quicksort의 평균 시간 복잡도는 O(NlogN)이다. 이것은 큰 컬렉션에 매우 효율적입니다.
O(N²)
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 =
무한대(실제로는) ms
배열에 요소 단 하나 추가만으로도 실행 시간이 매우 빠르게 증가한다.