시간 복잡도

점근적 실행 시간(asymptotic runtime) 또는 big-O 시간에 대한 개념

big-O,big-Θ,big-Ω

big-O : 시간의 상한
big-Ω : 시간의 등가 혹은 하한
big-Θ : big-O과 big-Ω 둘을 모두 의미한다.

공간 복잡도

알고리즘에서는 시간뿐만 아니라 메모리(혹은 공간)또한 신경 써야 한다.
공간 복잡도는 시간복잡도와 평행선을 달리는 개념이다.
크기가 n인 배열을 만들고자 한다면, O(n)의 공간이 필요하다.
nxn 크기의 2차원 배열을 만들고자 한다면, O(n^2)의 공간이 필요하다.

상수항은 무시하라!

big-O는 단순히 증가하는 비율을 나타내는 개념이므로, 특수한 입력에 한해 O(N)코드가 O(1)코드보다 빠르게 동작하는 것은 매우 가능성 있는 얘기다.
이러한 이유로 우리는 수행 시간에서 상수항을 무시해 버린다. 즉, O(2N)으로 표기 되어야 할 알고리즘을 실제로는 O(N)으로 표기한다.

지배적이지 않은 항은 무시하라!

O(N^2 + N)과 같은 수식이 있을 때는 어떻게 해야 할까?
두 번째 N은 틀림없이 상수항은 아니지만 그렇다고 특별히 중요한 항도 아니다.
즉, 수식에서 지배적이지 않는 항은 무시해도 된다.
O(N + logN) -> O(N)
O(5x2^N + 1000N^100) -> O(2^N)

재귀적으로 수행 시간 구하기

int f(int n){
	if (n <= 1){
    	return 1;
    }
    return f(n - 1) + f(n -1);
}

함수 f가 두 번 호출된 것을 보고 많은 사람들이 성급하게 O(N^2)이라고 결론 내릴 것이다.
하지만 완전히 틀렸다. 수행시간을 추측하지 말고 코드를 하나씩 읽어 나가면서 수행 시간을 계산해 보자. f(4)는 f(3)을 두 번 호출하고, f(3)은 f(2)를 두 번 호출한다. 총 호출 수를 표를 통하여 알아보자.

깊이	노드의 개수
0	1 = 2^0
1	2 = 2^1
2	4 = 2^2
3	8 = 2^3
4	16 = 2^4
...	... = 2^n

즉, 전체 노드의 개수는 2의 승수의 합으로 표현할 수 있다. (2^(N + 1) - 1)
다수의 호출로 이루어진 재귀 함수해서 수행 시간은 보통 O(분기^깊이)로 표현되곤 한다.
따라서 위의 경우에 수행 시간은 O(2^N)이 된다.