2장 : 복잡도 측정하기

최선의 경우를 바라되 최악의 경우를 대비하라
최선, 최악, 평균 이때 최악이 최소한이 기준점이 된다

계산에 드는 시간 측정하기

알고리즘의 시간 복잡도를 구하려면 알고리즘이 미지수 n크기의 입력량을 처리하기 위해 필요한 기초연산이 몇번인지 세면 된다

• 시간 복잡도: 알고리즘 실행 속도
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

증가율 추산

지배적항만으로도 T(n)의 근사치를 구할 수 있다

선택정렬 : $T(n) = n^2 + n -2$
지배적 항 : $n^2$
거품정렬 : $T(n) = 0.5n^2 + 0.5n$

약분한다면 선택정렬과 거품정렬이 둘다 $n^2$처럼 증가한다
곡선이 서로 가까워 지는 현상은 지배적 항이 동일할때 뿐이다
일차함수와 이차함수는 가까워지지 않는다

빅 - 오 표기법 : 시간,공간 복잡도의 증가율을 여러범주로 나누어 표현

• 지배적항이 $2^n$이하인 함수는 $o(2^n)$
• 이차함수$(n^2)$이하로 증가하는 함수는 $o(n^2)$
• 일차함수(n)이하로 증가하는 함수는 $o(n)$

이 표기법은 알고리즘이 최악의 경우 연산비용이 얼마나 되는지를 지배적 항으로 표현하는 데 사용된다
선택정렬과 거품정렬은 둘다 시간복잡도가 $o(n^2)$

상수시간 알고리즘 :
입력데이터의 크기와 관계없이 실행 시간이 일정한 경우 (증가율은 $o(1)$)

지수시간 알고리즘(증가율이 $o(2^n)$인 알고리즘 ) :
지수시간 알고리즘의 시간 복잡도는 너무 가파르게 증가 -> 실행 불가로 간주

계승시간 알고리즘(최악) :
시간복잡도가 $o(n!)$이다 np-완전 문제를 해결하기 위해서는 필요하다

공간복잡도 : 알고리즘을 실행하는데 필요한 작업 기억 영역의 양 공간복잡도는 시간 복잡도 분석과 비슷하게 구할수있다. 연산이 아니라 메모리를 센다는게 다르다
선택정렬의 공간복잡도는 $o(1)$이다
입력량에 관계없이 작업에 필요한 메모리가 항상 동일하다
메모리의 한계를 감안해 시간비용을 절충해야할 때가 있다