[Algorithm] 알고리즘의 시간복잡도
★알고리즘의 수행시간은 대체로 반복문에 의해 지배된다. N번 수행되는 반복문이 2개 중첩되면 수행시간은 N^2이다. 상수 시간은 그다지 중요하지 않으며 N + 100과 같은 경우는 사실상 N과 같기 때문에 그냥 N으로 표기한다.
★선형 시간 알고리즘 : 입력의 크기에 따라 일정한 비율로 수행시간이 증가하는 알고리즘이다. 주로 best 알고리즘인 경우가 많으며 수행시간은 N이다. 평균값 구하기 같은 문제가 대표적이다. z* ★선형 이하 시간 알고리즘 : 입력의 크기의 증가속도에 비해 수행시간 증가속도가 느린 알고리즘. 이진탐색같은 알고리즘이 있는데 이 알고리즘의 경우 수행시간은 log2(작은 2임..)N이다.
★다항 시간 알고리즘 : N의 거듭제곱을 사용한 다항식으로 실행시간을 나타낼 수 있는 알고리즘이다. 그러나 같은 다항 시간 알고리즘에서도 N과 N^100사이에는 엄청난 차이가 있어서 이 정의만으로는 아무 의미가 없으나 지수 시간 알고리즘와 구분하기 위해 사용하는 용어이다. 일반적으로 효율적인 알고리즘이라 인식되고 있다.
★지수 시간 알고리즘 : N이 1 증가할 때 수행시간이 몇 배로 증가하는 알고리즘이다. 대체로 효율적인 방법을 찾지 못한 알고리즘이다.
★시간 복잡도 : 알고리즘 실행 동안 수행되는 기본적인 연산의 수를 입력의 크기에 대한 함수로 나타낸 것이다. 시간복잡도는 알고리즘이 입력에 따라 시간이 얼마나 걸릴지를 근사적으로 알려준다.
★시간 복잡도가 높다는 말은 입력의 크기가 증가할 때 수행시간이 더 빨리 증가하는 말이다. 입력의 크기가 작은 경우 무의미할 수도 있다.
★O표기법 : 빅오 표기법이라고 읽더라. 알고리즘 수행시간 계산식이 보통 복잡하므로 가장 빨리 증가하는 항을 제외하고 상수를 포함한 나머지 항들은 모두 떼버리는 방법이다. 예를들어 (5/2)N^2 + Nlog(N/2) + 16N + 7은 O(N^2)인데, 최고차항을 빼고, 상수를 포함해 전부 없애버리기 때문에 근사값이지 정확한 시간은 아니다. n, 3n, (1/2)n은 모두 O(n)으로 똑같이 표기한다.
★코드가 단일명령어로 되어 있으면 O(1)로 표기한다.
★반복문이 k중으로 중첩되어 있으면 O(n^k)가 된다.
★여러 알고리즘이 단계별로 연결되어 있는 형태라면 전체 시간 복잡도는 시간 복잡도가 가장 큰 부분 알고리즘의 시간 복잡도와 같다.
★재귀함수의 시간 복잡도는 함수의 호출 횟수 * 한번 호출 시 소요되는 시간이다. 예를 들어 void g(int n) { if (n == 1) return; g(n-1); g(n-1); } 이 재귀함수는 맨 처음에 g(n)이 1번, 그 다음에는 g(n-1)가 2번, 그 다음에는 g(n-2)가 4번…호출되며 이를 일반화 시키면 g(n-k)은 2^k번 호출된다. n이 1일때 까지 반복하므로 k는 0~n-1의 값을 가지므로 총 소요시간은 2^0 + 2^1 + 2^2 + … 2^(n-1) = 2^n - 1이고, 시간 복잡도는 O(2^n)이다.
★여기서 잠깐. 시간 복잡도를 계산하다보면 등차수열과 등비수열의 합을 많이 계산하게 된다. 고등학교를 졸업한지 얼마 안됐지만 다 까먹었으므로 간단한 공식만 체크하고 가자.
- 초항이 a, 공차가 d인 등차수열의 n번째 항 까지의 합은 (2 * a + (n - 1) * d) / 2 * n이다.
- 초항이 a, 공비가 r인 등비수열의 n번째 항 까지의 합은 a * (1 - r^n) / (1 - r)이다.
★시간 복잡도를 미리 계산해 보면 문제를 풀 때 알고리즘을 직접 구현해 실행해 보지 않더라도 대략적인 수행시간을 알아볼 수 있다. 컴퓨터가 대략적으로 1초에 1억번의 연산을 한다고 대충 가정하기 때문에 이 이상으로 시간이 많이 소요될 것이라 판단되는 알고리즘은 걸러낼 수 있다. 물론 어디까지나 대략적인 추정치임을 염두해 두어야 한다.
★시간 복잡도는 엄밀히 말하면 최대 수행시간을, 즉 수행시간의 상한을 계산하는 방법이며 특정한 기준값 n0에 대해 n > n0가 성립하는 n0개 이상의 입력에 대해 알고리즘이 최대 c * f(n)번의 연산을 수행한다는 의미이다(이 때 c는 특정한 상수).
★연습문제 : 배열에 n개의 정수가 들어있을 때, 최대 부분 배열 합을 구하라. 이 때 부분 배열 합이란 배열 내부의 연속되어 있는 수들의 합을 말한다. 이 문제는 O(n^3), O(n^2), O(n)으로 풀수있는 알고리즘이 각각 존재한다. 모두 찾아보자. 분할정복법은 일단 배제한다…