알고리즘1 : time complexity, basic operation
학교 수업으로 알고리즘을 수강하게 되었다. 영어로 강의를 하셔서, 나름대로 정리를 해보고자 글을 쓴다.
알고리즘을 배우는 목표 다음과 같다.
CS(Computer Science)문제를 직면했을 때 우리는 알고리즘을 설계하게 된다. 하나의 문제에 대한 알고리즘은 복수개가 될 수 있다. 그런데, 여기서 우리는 효율성에 집중하여 어떤 알고리즘이 더 좋은 선택인지를 고민해간다.
알고리즘 효율성 선택에 대해 고민할 때 우리는 세가지 사고를 할 수 있다.
과학(=수학)적 사고
논리적 사고
체계적 사고
이렇게 세가지 사고를 거쳐나가는 올바른 생각 습관을 지녀 효율적인 알고리즘을 선택해 나간다.
CS 문제 하나가 주어졌다고 가정해보자. 이 문제는 답을 원하는 문제로 모델을 정해 해답을 얻어야 할 것이다.
이 해답이라는 것은
answer로 해석할 수도 있겠고, solution으로 해석할 수도 있다.
answer은 1개의 문제에 대한 답이고 solution은 여러 문제를 풀어내는 하나의 풀이 방식이다.
피보나치 수열을 이용하여 효율적인 알고리즘 개발의 중요성을 생각해보자.
피보나치 수열은 1 1 2 3 5 8 13 ... 이처럼 a(n+2)=a(n+1)+a(n) 이런식으로 진행되는 수열이다.
알고리즘을 짜서 아주 큰 항의 피보나치 수열을 찾으려면 어떻게 해야할까?
여러 알고리즘이 있겠지만, 2개의 알고리즘을 생각해보고 비교해보려 한다. (여기서는 5항을 구하는 문제를 가지고 알고리즘을 생각해볼 것임)
1. recursion(recursive) calls
a(5)=a(4)+a(3)
-> a(4)=a(3)+a(2) : a(3)
-> a(3)=a(2)+a(1)
a(2)와 a(1)은 1이라고 주어져 있을 것이기 때문에, 이렇게 전개를 해주고 다시 a(3)을 구하고, a(4)를 구하고 마지막으로 a(5)를 구하게 된다.
이는 2^(n/2) 시간복잡도를 갖는다.
2. bottom-up iteration
a(1)=1, a(2)=1, a(3)=1+1=2 ... a(5)=5 이렇게 구해나간다.
이는 O(n) 시간복잡도를 갖는다.
이렇게 여러개의 알고리즘을 생각해낸 뒤 어떤 알고리즘이 가장 효율적일지 고민해본다. 답은 2!
문제에 따라서 접근하고 설계하는 알고리즘은 당연히 달라질 수밖에 없다.
하지만 문제에 따라 best 알고리즘은 달라질 수 있다.
이 피보나치 문제에서는 2번 해답이 더 나은 알고리즘이었지만, 다른 문제에서는 1번 해답이 훨씬 나은 알고리즘이 될 수도 있다.
그래도 한가지 변하지 않는 것은, 모든 문제에는 최고의 알고리즘 즉 champion algorithm이 존재한다는 것이다.
알고리즘들은 각각의 장단점이 존재한다. 메모리를 많이 안쓴다거나, 시간이 적게 걸린다거나, 코드 길이가 짧다거나 등의 장점이 있을 것이다.
알고리즘의 효율성을 따지기 위한 기준으로 performance measure이 있는데 이론적인 속도를 표기할 때 O() 표기법이 있다. 이를 가지고 시간복잡도를 분석해나가는 것이다.
시간복잡도를 측정할 때는 이 시간복잡도는 외부에 의존해서 결정되어서는 안된다. 기계, 플랫폼, 프로그래머의 능력, 언어 등에 의존적이지 않고 입력 사이즈에 대한 제어만이 시간복잡도 결정에 관여해야 한다.
그래서 외부 의존적인 측면은 다 배제하고 Basic Operation(비교, 연산 등)에 집중해야 한다.
그리고 시간복잡도는 여러 방식으로 표현할 수 있다.
1. T(n) ; 모든 때에 적용이 가능한 시간복잡도
2. B(n) ; 최상의 경우일 때의 시간복잡도
3. W(n) ; 최악의 경우일 때의 시간복잡도
4. A(n) ; 평균적인 경우의 시간복잡도 -> 잘 안쓴다.