자바스크립트 알고리즘 Big-O 표기법

Big-O는 알고리즘의 성능을 수학적으로 표현해 주는 표기법이다. 알고리즘의 시간과 공간 복잡도를 표현 할 수 있다. 그리고 Big-O표기법은 알고리즘의 실제 러닝타임을 표시하는 것이 아닌 데이터의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표다.

1. O(1) - constant time

   데이터의 크기와 상관 없이 언제나 일정한 시간이 걸리는 알고리즘

2. O(n) - linear time

   입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘

3. O(n2) - quadratic time

   보통 n개의 데이터를 loop를 돌리면서 그 안쪽에 n번 만큼의 loop를 한번 더 돌리면 O(n2)의 시간복잡도의 알고리즘이라고 표현한다. 데이터와 시간과의 관계는 지수함수를 떠올리면 쉽다.

4. O(nm) - quadratic time (n의 m승)

   위 O(n2)의 2개의 변수 버전

5. O(n3) - polynomial / cubic time (n의 3승)

   위 O(n2)의 세제곱이니까 가로 세로 높이까지 추가된 시간복잡도로써 데이터가 늘어나면 O(n2)보다 처리시간이 더욱 급격하게 올라가게 된다.

6. O(2n) - exponential time (2의 n승)

   피보나치 수열 알고리즘을 재귀 형식으로 구현하면 O(2n)의 시간복잡도를 갖게 된다. O(n3)보다 데이터가 추가됨에 따른 처리 시간이 더더더더더욱 급격하게 올라가게 된다.

7. O(log n)

   오름차순으로 정렬된 숫자 배열에서 특정 수를 binary search로 찾는 알고리즘이 대표적인 O(log n) 알고리즘이다. 한번 처리가 진행 될 때마다 검색하야 하는 데이터의 양이 반씩 뚝뚝 떨어지 알고리즘을 O(log n)이라 한다. O(n)보다 효율적인 알고리즘으로 데이터가 늘어나도 성능이 크게 차이가 나지 않는 모습을 보여준다.

8. O(sqrt(n))

   O(n) 알고리즘에서 데이터 양의 제곱근의 순회만으로 풀리는 알고리즘이 O( sqrt(n) ) 알고리즘이다. 예를들어 숫자 36의 약수를 구하는 알고리즘을 1부터 36까지 모두 확인하면 O(n)지만, 약수가 대칭성을 보인다는 특징을 이용하면 36의 제곱근인 6번만의 순회만으로도 36의 약수를 모두 구할 수 있게 된다.