[C++] Sort 를 시작하기 전에 시간 복잡도가 무엇인지 알아보자
Sort 라는 것은, 말 그대로 무언가를 정렬한다는 것이다.
그리고 우리는 실생활에서도, 프로그래밍을 하면서도 데이터를 정렬할 일이 아주 아주 많다.
그렇기 때문에 우리는 Sort 에 대해 기본적으로 알고 넘어가야 한다.
컴퓨터에서 각종 데이터는 특정한 자료구조로 정의되어지기 때문에 우리가 그냥 보고 생각하듯이 정렬을 할 수 없다.
단순무식한 방법으로 컴퓨터에게 어떤 순서로, 어떤 데이터를 보고 비교하라고 알려 주어야 한다.
또한, 이러한 정렬 방법에 대해서는 예로부터, 그리고 지금까지도 많은 연구가 이루어지고 있다.
즉, 아직까지도 100% 완벽한 정렬 방법은 없다.
하지만, 그럼에도 불구하고 우리는 정렬을 해야 하기 때문에 기존에 연구되어진 정렬 방법들을 알고 넘어가야 한다.
일단, Sort 에 대해 깊이 파고들기 전에 우리는 먼저 "시간 복잡도" 에 대해 이야기 할 필요가 있다.
시간 복잡도란 우리가 작성한 코드가 얼마나 빠르게 실행되었는지
즉, 얼마만큼의 시간 성능을 가지는지를 의미한다.
예를 들어, 동일한 기능을 수행하지만 그 방법을 각각 다르게 작성해서
완료되는데 걸리는 시간이 다른 A, B라는 함수가 있다고 하자.
A라는 함수가 실행이 완료되는데 1초가 걸렸고,
B라는 함수가 실행이 완료되는데 2초가 걸렸다면
우리는 A 함수가 B 함수보다 더 빠르다, 즉 더 성능이 좋다고 할 수 있다.
(물론, 수행 시간이 빠르다고 해서 100% 더 좋은 함수인것은 아니다.)
그런데, 이렇게 성능을 비교하기 위해 반드시 함수를 실행시켜서 시간을 측정해 보아야만 할까?
또한, 입력의 변화에 따라 수행 시간은 변하기 마련인데 이를 어떻게 해야 "단일 성능" 단위로 말할 수 있을까?
이를 위해 고안해낸 방법이 Big-O (빅오) 표기법이라고 한다.
Big-O (빅오) 표기법
빅오 표기법이란, 입력의 크기가 1부터 무한대까지 증가하며 들어온다고 가정했을 때 걸리는 시간을 수학적으로 표기한 방법이다.
우리가 중, 고등학생때 배운 수학적 그래프를 생각해 보자.
예를 들어, $$ y=x $$ 라는 수식이 있다면, 여기서 X 는 입력 크기가 되고, Y 는 수행 시간이 된다고 정의하자.
즉, 입력 크기가 1일 때 1초가 걸리고 입력 크기가 2회일때 2초가 걸리는 수식이 탄생한다.
여기서 입력의 크기란, 원소의 갯수라고 생각하면 편하다.
이를 그래프로 나타내면 다음과 같다.
바로 이게 빅 오 표기법 중에서 O(n) 을 표기한 것이다.
입력 횟수와 시간이 정비례하는 그래프이다.
다음으로 $$ y = x^2 $$ 라는 수식을 생각해 보자.
이를 위의 그래프에 추가하면 다음과 같다.
바로 이게 빅 오 표기법 중에서 O(n^2) 을 표기한 것이다.
입력 횟수에 따라 수행 시간이 점진적으로 증가하는 그래프이다.
이 반대의 그래프는 $$ y = log(x) $$ 이 될 것이고, 이를 그래프로 그려보면
이렇게 표현할 수 있을 것이다.
이런 식으로 O(n^2) 의 그래프는 입력이 커지면 커질수록 그에 따라 실행 시간도 걷잡을 수 없이 커지며
O(log n) 은 입력이 커지더라도 그 실행 시간이 엇비슷하게 나온다는 것을 바로 확인할 수 있다 !
(따라서, O(n^2)의 시간 복잡도를 가지는 프로그램보다는 O(log n)의 시간 복잡도를 가지는 프로그램이 일반적으로 성능이 좋다고 말할 수 있다.)
따라서 우리는 어떠한 알고리즘의 성능을 표기할 때 이러한 빅 오 표기법을 사용하는 것이다.
이에 대한 사진은 아래를 참고하자.
즉, 우리는 Sort 라는 알고리즘을 포함한 모든 알고리즘에 대해 공부할 때, 이 시간 복잡도에 유의하여 생각할 필요가 있다.