Big-O 표기법
Big-O(빅-오)
Big-Ω(빅-오메가)
Big-θ(빅-세타)
위 세 가지 표기법은 시간 복잡도를
각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.
O(1)
Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다.
O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미다.
1 public int O_1_algorithm(int[] arr, int index) {
2 return arr[index];
3 }
4
5 int[] arr = new int[]{1,2,3,4,5};
6 int index = 1;
7 int results = O_1_algorithm(arr, index);
8 System.out.println(results); // 2O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다.
1 public void O_n_algorithm(int n) {
2 for(int i = 0; i < n; i++) {
3 // do something for 1 second
4 }
5 }
6
7 public void another_O_n_algorithm(int n) {
8 for(int i = 0; i < n * 2; i++) {
9 // do something for 1 second
10 }
11 }O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가한다. 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다.
그렇다면 함수 another_O_n_algorithm 은 어떨까요? 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가한다.
이것을 보고, "아! 그렇다면 이 알고리즘은 O(2n) 이라고 표현하겠구나!" 라고 생각할 수 있지만 그러나, 사실 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기한다.
입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다.
O(log n)
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있다.
1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정합니다).
50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
25보다 크므로 up을 외친다.
경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.
O(n^2)
O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.
예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n^2)라고 표현한다.
1 public void O_quadratic_algorithm(int n) {
2 for(int i = 0; i < n; i++) {
3 for(int j = 0; j < n; j++) {
4 // do something for 1 second
5 }
6 }
7}
8
9 public void another_O_quadratic_algorithm(int n) {
10 for(int i = 0; i < n; i++) {
11 for(int j = 0; j < n; j++) {
12 for(int k = 0; k < n; k++) {
13 // do something for 1 second
14 }
15 }
16 }
17 }O(2^n)
O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.
1 public int fibonacci(int n) {
2 if(n <= 1) {
3 return 1;
4 }
5 return fibonacci(n - 1) + fibonacci (n - 2);
6 }재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘이다.
