Big-O Notation (빅오 표기법)

복잡도(Complexity)는 크게, 

 

• 시간 복잡도 (Time Complexity)
• 공간 복잡도 (Memory Complexity)

의 2가지로 나눌 수 있는데, 요즘은 메모리 가격이 많이 낮아져서 공간 복잡도보다는 주로 시간 복잡도에 더 관심을 기울이는 편이다.

 

시간 복잡도란 즉, 어떤 알고리즘을 수행하는 데 얼마나 많은 절차(step)를 거쳐야하는지를 나타낸다.

시간 복잡도의 최선의 경우(best case)와 최악의 경우(worst case)를 생각했을 때, 최선의 경우는 별로 의미가 없다. 알고리즘을 수행할 때 최선의 경우가 발생하는 상황은 실질적으로는 드물기 때문이다. 평균(average case)도 생각해볼 수는 있겠지만 최악의 경우에 대한 유의미한 정보를 제공해주지는 않는다. 따라서 알고리즘 간의 성능 비교를 할 때, 최악의 경우, 즉 시간 복잡도의 상한선(upper bound)끼리 비교하는 것이 도움이 된다.

 

알고리즘을 수행하는 데 필요한 연산의 횟수, 즉 시간 복잡도는 "처리해야 하는 요소(item), 즉 데이터의 개수가 증가함에 따라 알고리즘의 규모가 얼마나 커질지"에 대해 알려준다.

 

빅오 표기법(Big-O Notation)이란, 어떤 알고리즘이 다루게 될 요소(item)의 개수와 연관된 복잡도(complexity)를 표현하는 방법이다.

 

만약 n개의 요소로 어떤 알고리즘을 수행할 때 필요한 총 연산 횟수를 (2n+2)라고 하면, n이 커짐에 따라 연산 횟수가 증가하며, (2n)에서의 2와 (+2)에서의 2는 상수다. 즉 n값의 변화와 관계가 없으므로 이것들은 시간 복잡도를 계산할 때 고려하지 않는다(버린다). 증가율에 영향을 미치는 것은 오로지 "n"이다.

 

따라서, 이 알고리즘의 시간 복잡도는 O(n)이다. O(n)은 다른 말로 선형시간 복잡도(Linear time complexity)라고도 한다.

 

Big-O
O(1)	Constant (BEST)
O(logn)	Logarithmic
O(n)	Linear
O(nlogn)	n log-star n
O(n^2)	Quadratic (WORST)

 

읽을 때는 "Big O of n"이라고 읽고, log의 밑(base)은 2다.

 

 

 

 

O(logn)은 거의 상수에 가까워 매우 빠르고, O(n)도 그럭저럭 나쁘지 않다. 하지만 O(nlogn)과 O(n^2)는 n이 커짐에 따라 필요한 연산 횟수가 상대적으로 빠르게 증가한다.