개관
알고리즘은 주어진 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것이며, 주관적이거나 모호한 것은 알고리즘이라고 할 수 없다. 가능한 명료하고 모호하지 않은 표현을 위해 사람들은 알고리즘을 대게 의사코드나 그것을 구현한 소스 코드의 형태로 설명한다.
이런 알고리즘을 평가하는 두 가지 큰 기준은 알고리즘이 사용하는 시간과 공간이다.
CH 04. 알고리즘의 시간 복잡도 분석
위 개관의 예시를 통해 알고리즘이 명료해야 한다는 것을 알고, 의사코드의 예시를 따로 찾아보면서 알고리즘을 어떻게 작성해야 하는지 확인하였다.
알고리즘을 평가하는 두 가지 기준인 시간(알고리즘의 수행속도)과 공간(메모리 공간)에 대해서 알고 있었지만 다시 한 번 상기하는 기회가 되었고, 뒷장의 알고리즘의 속도를 분석하는 방법과 알고리즘의 정당성을 증명하는 기술을 통해 알고리즘 속도에 대한 내용을 자세히 파악할 수 있었다.
1. 도입
이 책에서 좀더 빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 알고리즘의 속도를 어떻게 측정해야 할지 정하는 것이라고 한다. 이를 위한 가장 직관적인 방법은 두 프로그램의 수행시간을 측정하는 것인데, 프로그램 수행 시간 측정은 알고리즘 속도의 기준이 되기 부적합하다.
그 이유는 크게 2가지가 있는데 프로그램의 수행 시간은 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러 등의 수많은 요소에 의해 바뀔 수 있기 때문이며, 프로그램의 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못하기 때문이다.
그렇다면 어떤 것이 알고리즘의 속도의 기준이 될까? 이는 바로 프로그램 안의 반복문이 수행되는 횟수이다. 입력의 크기가 커질 수록 반복문이 알고리즘의 수행 시간을 지배하기 때문에 반복문이 수행되는 횟수가 알고리즘의 수행 시간이 되는 것이다.
2. 선형 시간 알고리즘 & 3. 선형 이하 시간 알고리즘 & 4. 지수 시간 알고리즘
이 챕터에서는 알고리즘의 수행 시간의 대표적인 형태 3가지를 살펴본다.
• 입력의 크기에 대비해 걸리는 수행 시간이 비례하는 선형 시간 알고리즘
• 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 선형 이하 시간 알고리즘(이진 탐색 알고리즘이 여기에 속함)
• 입력의 크기가 증가할 때마다 걸리는 수행 시간이 배로 증가하는 지수 시간 알고리즘
5. 시간 복잡도
시간 복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행되는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것이다. 여기서 기본적인 연산은 더 작게 쪼갤 수 없는 최소 크기의 연산이다.
시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다는 의미인데, 이는 시간 복잡도가 낮다고 해서 언제나 빠르게 동작하는 것이 아니라 시간 복잡도가 낮은 알고리즘이 입력이 커지면 커질 수록 더 효율적이라는 말이다. 시간 복잡도를 간편하게 표기하는 방식으로 점근적 시간 표기 : O표기가 있다.
