Week 5
시간 복합도에 관한 강의였다.
시간 복합도는 프로그램이 실행되는 시간에만 집중한 것으로 Input에 따라 Best Case, Worst Case, Average Case로 계산 될 수 있다.
이후 Random Access Model 이 나온다. Random Access Model 이란 Count Machine 같은 모델인데 컴퓨터가 실행하는 코드를 순서대로 count 하는 것이다. 이 때 실행시간(CPU 의 성능, OS의 성능,python 이나 java 같은 언어의 성능)은 무시되고 오직 step 만을 계산하는것이다.
위의 가정하에서 Random Access Model 에서는 시간 복합도를 input 의 크기 n 에 대해 a*n +b 나 n^2+4 처럼 나타낼 수 있는데 강의에서는 Worst Case에 집중한다.
Worst Case(input N이 굉장히 클때)에서는 a*n+b 에서 계수 a나 상수 b는 의미없는 수이다. 마찮가지로 a*n^2 +5 에서 계수 a나 상수 5는 의미없고 n^2만이 의미를 가지게 된다.
이럴때(Worst Case에서) 시간 복합도를 표현하기 위해 빅 O표현법(Big O Notation)을 사용하는데 a*n^2 +5의 경우 O(n) 으로 n^2+4의 경우 O(n^2)로 나타낼수 있다.
Instance N 에 따라(정확히 무슨말인지 모르겠다 ㅠ) 알고리즘은 아래와 같이 빅 O로 표현될 수 있는데
위 의표는 그 알고리즘을 나타낸 표이다.
효율성의 측면에서 상수형으로 표현되는 알고리즘이 가장 좋은 알고리즘이고 지수형으로 표현 되는 알고리즘이 최악의 알고리즘이다.(하지만 경우에 따라 지수형으로 표현 할 수 밖에 없는 알고리즘도 존재한다 ex. 하노이의 탑)
N이 굉장히 클때 그 차이는 굉장히 크기 때문에 가능하다면 찾을 수 있다면 로그형이나 선형 알고리즘을 찾아 해결하는 것이 시간복합도 측면에서 효율적인 알고리즘이라 할 수 있다.
강의가 진행될수록 뭔가 수학적 개념이 자주 나오고 이해하기 어려워지고.. 쉽지 않구만
위의 표는 http://skmagic.tistory.com/164 에서 퍼왔다. 이 분 블로그 타이틀이 무섭더라.
“자기개발을 멈추면 죽는다.”