Algorithms / 알고리즘 복잡도 분석

알고리즘이 몇개 있다고 하였을 때, 제일 효율적인 하나를 선택해야하는 경우에
직접 구현하지 않아도 대략적으로 알고리즘의 효율성을 비교하면 좋다.
이를 알고리즘의 복잡도 분석(Complexity analysis)로 가능하다.

알고리즘 분석은 2가지 측면을 고려할 수 있다.

- 시간 복잡도(time complexity): 알고리즘의 수행 시간 분석
- 공간 복잡도(space complexity): 알고리즘이 사용하는 기억공간 분석

주로 알고리즘의 복잡도를 이야기할 때 대개는 시간 복잡도를 이야기한다.
알고리즘이 차지하는 공간보다는 수행 시간에 더 관심이 많기 때문이다.

연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간 복잡도 함수라 하고 이를
T(n)이라 표기한다.

하나의 루프 제어문은 1개의 대입 연산, n+1개의 비교 연산(루프를 빠져나가기 위해서
추가), n개의 덧셈연산을 포함하고 전체적으로 2n+2번의 연산을 하나, 2n과 n은 n의
개수에 따라 미미하므로 빅오표기법(big-oh notation)에 의해 n이라는 수행시간을
가진다고 한다. 즉 다항식의 최고차 항만을 취한다.

O(1):상수형
O(logn):로그형
O(n):선형
O(nlogn):선형로그형
O(n^2):2차형
O(n^3):3차형
O(2^n):지수형
O(n!):팩토리얼형

알고리즘 수행시간은 다음과 같다.

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)