알고리즘(2) - 알고리즘 설계와 기초 분석

바람직한 알고리즘

주어진 문제를 체계적인 절차로 해결했다고 해서 모든 알고리즘이 바람직하다고는 할 수 없다. '좋은 알고리즘'의 특성은 다음과 같다.

• 모호하지 않고 이해하기 쉽도록 명확해야 한다.
• 같은 문제를 해결하는 알고리즘 사이에 수행시간 수백 배 차이가 날 수 있다. 가장 적은 수행시간을 갖는다.

 알고리즘 분석

알고리즘의 타당성을 확인하기 위해 알고리즘을 분석할 필요가 있다. 여기서 '소요시간(수행시간)'이 가장 중요하다.

알고리즘 a는 연산시간 1/5초 걸릴 수 있고,

알고리즘 b는 연산시간 5초 걸릴 수도 있다.

알고리즘 a와 b의 수행시간 비교 그래프

n의 값 25를 기점으로 수행시간에 현저한 차이를 보인다.

 

재귀와 귀납적 사고

재귀란, 자기호출(recurrence)이며, 어떤 문제 안에서 크기만 다를 뿐 성격이 똑같은 작은 문제 포함되어 있는 것을 의미한다.

 

팩토리얼 factorial이 재귀적 구조의 예이다. 식으로 표현하면 다음과 같다. N! = N * (N-1)!

 

점근적 분석 Asymptotic analysis

크기가 작은 문제의 경우, 어떤 알고리즘을 사용해든 무방하다. 효율성을 따질 필요가 없기 때문이다. 그러나 크기가 큰 문제의 경우엔? 효율성이 중시된다. 사용할 알고리즘이 비효율적이라면 시간적인 면에서 치명적이다.

그렇기에 입력의 크기가 클 경우에 대한 분석을 점근적 분석이라 한다.

 

점근적 표기법은 다음과 같이 나뉜다.

• O-표기법 (빅오라고 한다.) : 점근적 증가율이 f(n) 이하인 모든 함수의 집합이다. O(n)={n, n log n}. n과 n log n도 O(n)이다.
• 오메가 표기법 : 점근적 증가율이 f(n) 이상인 모든 함수의 집합이다. 빅오와 대칭된다. O(n^2)라면, n^2 이상이 전부 Ω(n^2)에 속한다.
• 쎄타 표기법 : 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합이다. 즉, 알고리즘의 소요시간이  θ(n)이라면 약 n정도의 시간이 걸린다는 것이다.
• 리틀 O 표기법 : 차수가 f(n) 미만을 의미한다. 자세히 말하자면 점근적 의미에서 함수증가율이 어느 한계보다 더 작음을 의미한다. O(n^3)=n^2
• 리틀 오메가 표기법 : 리틀 O와 대칭이다. 어느 한계보다 함수 증가율이 더 큼을 의미한다. n^2 = ω(n)

 

알고리즘의 수행시간을 표현할 때  시간 복잡도(time complexity)로 나타낸다. 자료구조에 따라 검색 연산의 시간복잡도가 다르다. 시간복잡도 분석의 종류는 다음과 같다.

• 최악의 경우 worst-case : 이 경우 입력에 대해 수행시간을 분석한다.
• 평균의 경우 average-case : 모든 입력에 대해 분석한다. 최악의 경우보다 분석이 까다롭다.
• 최선의 경우 best-case : 최선의 경우에 대한 입력의 수행시간을 분석한다. 유용하진 않다고 한다.