[자료구조] 빅오 표기법(Big-O notation)이란?

빅 오 표기법의 정의

Big-O notation은 알고리즘의 시간 복잡도를 나타내는 표기법이며, O(f(n))으로 나타낸다.

그런데 여기서 시간 복잡도란 무엇일까?

 

 

시간 복잡도

알고리즘 분석에서는 2가지의 측면을 고려할 수 있다. 알고리즘의 수행시간과 알고리즘이 필요로 하는 기억 공간의 양이 그것이다. 알고리즘 수행 시간 분석을 시간 복잡도(time complexity)라고 하고 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도(space complexity)라고 한다. 대게 알고리즘이 차지하는 공간보다 수행 시간에 더 관심이 있기 때문에 알고리즘의 복잡도는 대게 시간 복잡도를 말한다.

시간 복잡도는 알고리즘의 절대적인 수행 시간을 나타내는 것이 아니라(000ms) 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는지 숫자로 표시한다. 즉 알고리즘 내 연산의 횟수와 관계있다.

 

 

예를 들어 양의 정수 n을 n번 더하는 문제를 생각해보면 아래의 3가지 알고리즘으로 나타낼 수 있다.

알고리즘A	알고리즘B	알고리즘C
sum = n * n;	for(i = 1; i <= n; i++) {     sum = sum + n; }	for(i = 1; i <= n; i++) {     for(j = 1; j <= n; j++) {        sum = sum + 1;     } }

 

 

해당 코드를 가지고 아래와 같이 알고리즘을 분석해보면 전체 연산 수는 아래와 같다.

	알고리즘A	알고리즘B	알고리즘C
대입 연산	1	n	n*n
덧셈 연산		n	n*n
곱셈 연산	1
나눗셈 연산
전체 연산 수	2	2n	2n^2

하나의 연산이 t만큼의 시간이 걸린다고 하면 알고리즘A는 2t에 비례햐는 시간이, 알고리즘 B는 2nt의 시간이, 알고리즘 C의 연산은 2n^2 * t 만큼의  시간이 걸린다. 

따라서 n이 커질수록 알고리즘간 속도의 차이는 커지게 된다.

 

 

알고리즘의 시간 복잡도 함수

 

---

Big - O 표기법

자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른 항들은 상대적으로 무시될 수 있다.

예를 들어 T(n) = n^2 + n + 1 인 경우 n = 1000 일 때 T(n)의 값은 1001001이고 이 중에서 n^2의 값이 전체의 99.9%를 차지하고 있음을 알 수 있다.

따라서 시간복잡도에서는 차수가 가장 큰 항만을 고려하면 된다.

 

시간복잡도 함수에서 중요한 것은 n이 증가하였을 때에, 연산의 총 횟수가 n에 비례하여 증가하는지, 아니면 n^2에 비례하여 증가하는지, 아니면 다른 증가 추세를 가지는지가 더 중요하다.

결국 시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법을 빅오 표기법이라고 한다. 즉, 알고리즘이 n에 비례하는 수행 시간을 가진다고 말하는 대신에 알고리즘 A의 시간 복잡도가 O(n)이라고 한다.

 

표기법 예시

최고차항의 계수도 버리고 단지 최고차항의 차수만을 사용한다.

ex. 1) 7n - 3 = O(n)

ex. 2) 8 * n^2 * logn + 5 * n^2 + n = O(n^2 * logn)

 

알고리즘의 수행시간 비교

O(1) < O(logn) < O(n) < O(n*logn) < O(n^2) < O(2^n) < O(n!)

 

 

---

 

참고 자료:

https://holika.tistory.com/29

[자료구조] 빅오 표기법(Big-O notation)이란?

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=183868288&start=slayer 

C언어로 쉽게 풀어쓴 자료구조