시간복잡도(Big-O notation)
Big-O notation 이란?
알고리즘의 시간 복잡도를 나타내며, O(f(n)) 으로 나타낸다.
여기서 말하는 시간 복잡도란 연산의 횟수와 관계가 있다.
알고리즘 내에서 시간 복잡도를 계산할 때에는 단위 연산의 횟수를 기준으로 하는데, 단위 연산이란 정의, 단순 계산, 비교, 출력 등 가장 간단한 연산들을 의미한다.
알고리즘을 작성하는데 가장 중요한 부분은 효율성을 증가시키는 것인데, 시간 복잡도를 알아냄으로써 그것들을 비교할 수 있다.
Big-O 의 표기법에는 표준적으로 따라야 하는 법칙들이 몇가지 있다.
1. f(n)이 n에 대한 d차식이면, f(n)은 O(n^d) 이다.
2. 가능한 가장 작은 notation을 사용하여야 한다.
ex) O(n^2)도 되고, O(n)도 된다면 가장 작은 O(n)을 사용해야한다.
3. 가능한 가장 간단한 표기를 사용하여야 한다.
ex) O(3n+4)도 되고 O(n)도 된다면 가장 간단한 O(n)을 사용해야한다.
위의 법칙들에 따라서 Big-Oh 표기법은 보통
O(1), O(log n), O(n), O(n^2), O(n log n) , O(n^3), O(2^n) 등으로 쓸 수 있다.
위 예들의 시간 복잡도를 비교해보면
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) 의 순서로 복잡하다.
마지막으로 알고리즘 내에서 간단하게 시간 복잡도를 계산하는 법을 알아보겠다.
일일이 모든 연산을 세는 것은 의미가 없다. 왜냐하면 루프 밖에 있는 단순 연산들은 결국 상수항이라 제외되고, 루프 안에 여러개의 연산이 있다고해도 가장 큰 차수 외에는 각 항의 계수를 포함해서 모든 것들이 무시 되기때문이다.
즉, 루프와 재귀의 횟수만 확인하면 된다.
예를들어 n에 관련된 for 루프가 두 번 있다면 n에 대한 1차식 두 개를 곱하므로, 연산의 개술에 대한 식은 n에 대한 2차식이 되고, 이는 O(n^2)가 된다.
알고리즘 내에서 시간 복잡도를 계산할 때는 항상 worst-case를 가정하고 계산한다.
즉, 가장 오래 걸릴 경우의 시간 복잡도를 구한다는 뜻이다.