알고리즘이란, 어떤 문제를 해결하기 위한 여러 동작들의 모임이다.
컴퓨터 과학에서 알고리즘은 얼마나 효율적으로, 얼마나 더 빨리 문제를 푸느냐가 좋은 알고리즘의 지표가 된다.
알고리즘의 효율성이 얼마나 중요한지 몇가지 예를 들어 설명하겠다.
숫자 X 가 N개의 숫자가 들어있는 리스트 S에 있는지 찾을 때.
이 문제를 풀기 위해서는 순차 검색 알고리즘과과 이진 검색 알고리즘을 사용할 수 있다.
이 알고리즘을 사용하기 앞서, 리스트는 오름차순으로 정렬 되어있다고 가정한다.
input 크기에 따른 2가지 검색 알고리즘을 비교하였을때 다음과 같이 나타낼 수 있다
Array Size(n) |
Sequential Search |
Binary Search |
2^7 |
2^7 |
8 |
2^10 |
2^10 |
11 |
2^20 |
2^20 |
21 |
2^32 |
2^32 |
33 |
input 값이 커질수록 순차 검색 알고리즘이 검색 해야 할 양이 많이지면서, 검색에 오랜 시간이 걸린다.
반면 이진 검색 알고리즘은 순차 검색 알고리즘에 비해 적은 시간으로 검색 할 수 있다.
또 하나의 예를 소개하겠다.
피보나치 수열을 구하는 방법에는 2가지 알고리즘을 사용할 수 있다.
재귀 알고리즘과 반복 알고리즘이다.
재귀 알고리즘이란 하나의 함수에서 자신을 다시 호출하여 문제를 풀어나가는 기법이다.
재귀 알고리즘을 이용해 피보나치 수열을 구하면
T(n) > 2 * T(n-2)
T(n) > 2 * 2 * T(n-4) ....
T(n) > 2 * 2 * 2 * 2 * T(0) = 2^(n/2) 번 계산하고
반복 알고리즘을 이용해 피보나치 수열을 구하면
T(n) = n+1 번 계산한다.
걸리는 시간을 표로 정리하면 다음과 같다.
n |
Iteration |
Recursion |
60 |
61ns |
1s |
100 |
101ns |
13days |
200 |
201ns |
4*10^13 yrs |
재귀 알고리즘으로 피보나치 문제를 풀 경우, 엄청난 시간이 걸린다.
따라서 어떤 문제를 풀때, 어떤 알고리즘으로 풀지는 잘 선택해야 한다.