알고리즘의 효율 분석

알고리즘 수행 시간 측정 방법

알고리즘의 시간 측정은 '절대 시간'을 측정하는 방법과 '시간 복잡도'를 측정하는 방법이 존재한다. '절대 시간'은 말 그대로 프로그램과 프로그램 사이의 걸리는 시간을 측정하는 방법이다. '시간 복잡도'는 알고리즘이 시작한 순간부터 결과 값이 나올 때까지 연산 횟수를 의미한다. 코딩 테스트를 위한 알고리즘에서는 거의 대부분 시간 복잡도로 평가한다.

 

시간 복잡도

시간 복잡도(Time Complexity)란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 시간 복잡도는 주로 점근적 표기법을 사용하여 나타낸다. 

 

시간 복잡도 측정

1차원 배열의 맨 앞부터 하나씩 검사하는 알고리즘이라고 가정해보자. 이런 경우, 입력이 1일 때는 시간복잡도가 1이고, 입력이 8일 때는 시간복잡도가 5이다. 

따라서, 특정 상황에 대한 연산 횟수는 특정 상황에 한정한 것이기 때문에 무의미하다. 

시간 복잡도는 알고리즘이 시작한 순간부터 결과 값이 나올 때까지의 연산 횟수를 타나낸다. 특정 상황(특정 입력 크기)에 한하지 않고 시간 복잡도를 표현하기 위해서, 입력 크기를 N으로 일반화하여 연산 횟수를 나타내야 한다. 이처럼 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방식을 점근적 표기법이라고 한다. 그리고 시간 복잡도를 측정한 결과는 최선, 보통, 최악의 경우로 나눈다. 

 

빅오 표기법 (big-O notation)

빅오 표기법은 상한선을 활용하는 방법이다. $O( n^2)$은 최고차항의 차수가 $n^2$을 넘지 않은 모든 함수의 집합을 뜻한다. 어떤 알고리즘에서 입력의 크기가 n이라고 할때, 이 알고리즘이 충분히 큰 입력에 대해 어떤 경우든 $O(n^2)$에 비례하는 시간을 초과하지 않는다면 이 알고리즘의 수행 시간은 $O(n^2)$이라고 말한다. 따라서 알고리즘의 연산 횟수가 n, nlogn인 경우도 $O(n^2)$d에 포함되는데, 이런 경우 정보의 손실이 발생한다. 

 

그럼 위 1차원 배열의 맨 앞부터 하나씩 검사하는 알고리즘은 $O(n)$으로 표기할 수 있다. n항보다 더 높은 차수거나 지수함수, 로그함수도 있지만, 저렇게 표기하는 방법이 가장 정보의 손실이 적게 발생한다. 

예시) $O(n^2)$ :  $n^2, n, 7n^2-100n, 3n^2-7nlogn$

 

빅오메가 표기법 ($\Omega$)

빅오메가는 빅세타와 정반대로 하한선을 이용하는 방법이다. $\Omega(n^2)$은 최고차항의 차수가 $n^2$보다 작지 않은 모든 함수의 집합이다. 따라서, $n^2-7n-8, 7n^3-100n, 10n^100$등의 함수가 포함되고 정보의 손실이 클 수 있다. 

 

빅세타 표기법($\Theta$)

빅세타는 하한과 상한을 다 이용하는 방법으로, 빅오와 빅세타의 교집합으로도 볼 수 있다. $\Theta(n^2)$에는 $n^2-7n-8, n^2+100nlogn, 100n^2$등의 함수가 포함된다.

 

점근적 표기법의 수학적 정의

대부분의 점근적 표기는 수학적으로 정의된다. 

충분히 큰 모든 n에 대해 $f(n) \leq cg(n)$인 양의 상수 c가 존재한다는 의미이다. 이 수학적 정의는 알고리즘의 복잡도를 증명할 때 요긴하게 사용된다.