Big-O

 Big O 표기법은 알고리즘의 시간복잡도나 공간복잡도를 설명하는데 사용되는 도구이다. Big-O는 알고리즘의 시간복잡도의 상한을 표현하는 방법으로, 알고리즘의 최악의 상황을 분석한다. 입력 크기에 따라 알고리즘에 걸리는 시간의 상한을 O(f(n))으로 표기하는데, 여기서 f(n)은 알고리즘이 크기 n의 문제를 해결하기 위해 수행하는 연산의 수를 나타내는 함수이다.

 

Big-O의 정의

 두 함수 f(n)과 g(n)이 주어졌을 때, f(n) <= c*g(n) 이고 모든 n>=n_0 에 대해 f(n)이 c>0 이고 n_0>=0 인 상수가 존재할 때 f(n)은 O(g(n)) 이라고 한다.

 간단히 말해서, c와 n_0이 상수인 모든 n>=n_0 에 대해 f(n)이 c*g(n) 보다 더 빨리 증가하지 않으면 f(n)은 O(g(n)) 이다.

 수학적으로 설명하면 어렵지만, 가슴으로 느끼면 쉽다. 예를 들어, f(n) = 3n^3 + 5n +7이고, g(n) = n^2라고 하면, f(n)의 가장 큰 항인 3n^2이 f(n)의 전체 성장 속도를 결정하고, 어떤 큰 n에 대해서는 f(n)이 결국 4*g(n)보다 작아지도록 만드는 상수 c와 n_0을 찾을 수 있다. 따라서 f(n) = O(n^2)라고 할 수 있다.

 

 Big-O 표기법은 알고리즘의 효율성을 분석하는데 도움이 된다. 컴퓨터가 처리하는 데이터는 크기가 큰 경우가 많기 때문에, 큰 수 n에 대하여 함수의 성장세를 나타내는 Big-O 표기법이 유효하게 적용된다.

 

 자주 사용되는 시간복잡도는 다음과 같다.

1. 선형 시간 복잡도 O(n)
2. 대수 시간 복잡도 O(log n)
3. k차 시간 복잡도 O(n^k)
4. 지수 시간 복잡도 O(2^n)
5. 팩토리얼 시간 복잡도 O(n!)

 일반적으로 아래로 갈수록 복잡한 알고리즘이다.

 

 Big-O표기법을 사용해서 알고리즘의 성능을 예상해볼 수 있다. 

 어떤 함수를 분석해보았을 때 Big-O가 O(n^2)이 나왔다고 생각해보자. 우리가 예상하는 입력의 크기가 10만개일 때, 이 프로그램의 실행에 걸리는 시간은 대략적으로 10만*10만 / 40억 = 2.5초 정도 걸릴 것이라 예상할 수 있다. 10만*10만은 입력의 크기 10만을 n^2한 것이고, 40억은 CPU가 1초에 처리할 수 있는 명령의 수이다.(CPU의 클럭이 4GHz라고 가정)
 우리가 이 함수를 웹서버에서 실행한다고 하면 클라이언트는 네트워크 지연 + 2.5초만큼의 시간을 기다려야 할 것이다. 이것은 이상적이라 볼 수 없다. 우리는 더 나은 알고리즘을 찾을 필요가 있을 것이다.