[자바스크립트] 알고리즘 빅오 표기법 (big-O notation)

빅오 표기법 (big-O notation) 이란?

빅오 표기법은 보통 알고리즘의 시간(Time) 복잡도와 공간(Space) 복잡도(complexity)를 나타내는데 주로 사용 된다. 알고리즘의 러닝타임에 상관없이 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이기 때문에 상수와 같은 숫자는 모두 1이 됩니다.

 

 

O(1)의 시간복잡도 Constant time

입력데이터의 크기와 상관없이 언제나 일정한 시간이 걸린다. 가로축의 데이터 크기 세로축이 시간이라고 할 때 데이터가 증가함에 따라 성능의 차이가 없다.

 

O(n)의 시간복잡도 Linear time

입력데이터의 크기와 비례해서 처리시간이 걸리는 알고리즘의 표현할 때 사용.  n개의 데이터를 받으면 n번 루프를 도니까 n이 늘어날 때 마다 처리가 하나씩 늘어나서 n이 늘어나는 만큼 처리시간도 늘어난다.

항상 데이터와 시간이 비례해서 증가하기 때문에 그래프는 상승하는 직선으로 표현된다.

 

O(n2)의 시간복잡도 Quadratic time

n개의 데이터를 받으면 각각의 엘리먼트에서 n번씩 또 돌아서 데이터가 커지면 커질수록 처리시간의 부담이 커진다.

O(n2)의 시간복잡도

 

O(nm)의 시간복잡도 Quadratic time

n스퀘어와 비슷해 보이지만 n을 m만큼 돌린다. 데이터가 커지면 커질수록 처리시간의 부담이 커진다.

O(nm)의 시간복잡도

 

O(n3)의 시간복잡도 Polynomial / Cubic time

n의 제곱에 n을 한번더 돌리기 때문에 큐빅모양으로 처리한다.

O(n3)의 시간복잡도

 

O(2ⁿ)의 시간복잡도 Exponential time

피보나치 수 는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열로, Fn = Fn-1 + Fn-2이라는 공식으로 표현됩니다.
수열의 처음 두 숫자는 1이고, 그 다음 항들은 2(1+1),3(1+2),5(2+3)가 됩니다(1, 1, 2, 3, 5 , 8, 13, 21 ...).
피보나치 수는 황금 비율 등의 우리 주변을 둘러싼 수많은 자연 현상과 관련이 있습니다.

피보나치 수열

O(log n)의 시간복잡도 Binary search(이진검색)

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

이진 탐색은 순차 탐색에 비해 엄청나게 빠른 속도로 원하는 데이터를 찾을 수 있다.
한 번에 엄청나게 많은 데이터를 검색 범위에서 줄일 수 있기 때문에 1부터 100사이의 숫자 중 검색한다면 어떤 숫자를 찾던지 최대 7번 만에 정답을 찾을 수 있다.

 

 

Big-o 시간복잡도 순위