빅오(Big-O)표기법 - 최악의 경우에도 이 정도의 퍼포먼스를 보장해!

빅오(Big-O)표기법 - 최악의 경우에도 이 정도의 퍼포먼스를 보장해!

빅오(Big-O)표기법 - 최악의 경우에도 이 정도의 퍼포먼스를 보장해!

Big-oh를 항상 생각하는 계획적인 사람

취업 준비 당시 필자의 슬로건이었던, Big-oh에 대해 포스팅 해보려 한다.

본인은 어떤 일을 계획할 때 최악의 경우의 수부터 생각을 하는 편인데,

Big-oh는 바로 이러한 최악의 경우에 보장하는 성능을 나타내는 지표로 알고리즘의 효율성을 나타낸다.

이러한 알고리즘의 성능을 나타내는 데에는 시간복잡도와 공간복잡도가 있는데 각각은 다음을 의미한다.

시간복잡도(Time Complexity)는 알고리즘의 수행시간

공간복잡도(Space Complexity)는 알고리즘의 메모리 사용량

Big-O표기법은 두 가지 복잡도 중 시간복잡도를 나타내는 표기법이며 입력값 N에 대해 알고리즘의 성능을 나타낸다.

출처 : 구글 이미지 검색

알고리즘의 성능은 다음과 같다.

O (1) > O (logn) > O (n) > O (nlogn) > O (n^2)  > O (n^3) > O (2^n) > O (n!)

즉, n^n에 가까울수록(그래프가 위로 올라갈수록) 성능은 떨어지고, 1에 가까울수록(그래프가 내려갈수록) 성능은 올라간다.

물론, 특정 상황의 입력 값에 따라 실제 소요되는 시간이 다를 수는 있다.

예를 들면,

1, 5, 10 3가지의 숫자를 가지고 정렬을 하는 것은 시간복잡도 n^2을 가지는 정렬방식이 logn을 가지는 정렬방식 보다 빠를 수 있다.

그래서, 시간복잡도는 이러한 상황을 제외하고 충분한 데이터 집단을 가지고 있다는 가정하에 표기한다.

O(1)을 가지는 알고리즘은 세상에 없다고 봐야한다.

왜냐하면, 5만개의 랜덤하게 나열된 숫자를 한 번에 정렬하는 알고리즘은 없기 때문이다.

정렬 알고리즘으로 예를 들었을 때,

1번 수행 당 n번의 정렬을 수행한다고 생각하면 된다.

8번의 정렬을 수행한다고 가정할 경우 시간복잡도는 다음과 같이 계산 될 수 있다.

	logn	n	nlogn	n^2
횟수	3	8	24	64

즉, 정리하자면

logn은 데이터 수에 따라 연산 횟수가 낮고

n은 데이터 수와 연산 횟수가 같고

nlogn은 데이터 수와 거의 비례하며

n^2은 데이터 수에 비해 연산 횟수가 2배가 된다.

알고리즘 중 최악의 경우 퀵, 합병정렬이 nlogn을, 선택,삽입정렬이 n^2의 시간복잡도를 갖는데,

다음의 표를 통해 속도 차이를 느낄 수 있다.

출처 : https://www.toptal.com/developers/sorting-algorithms

각 알고리즘에 대한 설명은 차후 포스팅에 이어 진행하도록 하겠다.

이제 누군가 당신이 만들 프로그램은 얼마나 효율성이 좋나요? 라고 문의하였을 때

제가 만든 프로그램은 최소한 logn의 퍼포먼스는 보장합니다.

라고 간지나게 대답하면 된다.