시간복잡도
문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 : 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?
효율적인 알고리즘을 구현했다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소한 알고리즘을 구성했다는 것.
Big-O 표기법
시간복잡도를 표기하는 방법: Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타)
위 세가지 표기법은 시각 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법. 이 중에서 Big-O 표기법이 가장 자주 사용됨. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문. "최소한 특정 시간 이상 걸린다" 혹은 "이 정도 시간이 걸린다" 를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응 가능함.
결과를 반환하는데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정함. 이 알고리즘을 100번 실행한다면 최선의 경우 100초가 걸림. 만약 실제로 걸린 시간이 1시간을 넘긴다면 어디에서 문제가 발생한 것인지 의문이 발생함. 최선의 경우만 고려하였으니 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야하므로 많은 시간이 필요함.
평균값을 기대하는 시간 복잡도를 고려한다면 알고리즘이 100번 실행할 때마다 100분의 시간이 소요된다고 생각했는데 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 하게 됨.
극단적인 예이지만 위와 같이 최악의 경우를 발생하지 않기를 바라며 시간을 계산하는 것보다는 '최악의 경우도 고려하여 대비'하는 것이 바람직함. 따라서 다른 표기법보다 Big-O 표기법을 많이 사용함.
O(1)
Big-O 표기법은 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는가?'를 표기하는 방법. O(1)은 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않음. 입력값의 크기와 상관없이, 즉시 출력값을 얻어낼 수 있다는 의미.
public int O_1_algorithm(int[] arr, int index) {
return arr[index];
}
int[] arr = new int[]{1,2,3,4,5};
int index = 1;
int results = O_1_algorithm(arr, index);
System.out.println(results); // 2위 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있음. 예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 결과를 반환할 수 있음
O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미함. 예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있음.
public void O_n_algorithm(int n){
for (int i = 0; i < n; i++) {
// do something for 1 second
}
}
public void another_O_n_algorithm(int n) {
for(int i=0; i < n * 2; i++) {
// do something for 1 second
}
}O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가함. 즉 입력값이 증가함에 따라 '같은 비율로' 걸리는 시간이 늘어남. 함수 another_O_n_algorithm은 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가함. 이 알고리즘은 O(2n)이라고 표현할 수 있다고 생각하겠지만 이 또한 O(n)으로 표기함. 입력값이 커지면 커질수록 계수(n앞에 있는 수)의 의미(영향력)이 점점 퇴식되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기함.
O(log n)
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법 중 O(1) 다음으로 시간 복잡도를 가짐. BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법).
O(n^2)
O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미. 예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n^2)라고 표현함.
public void O_quadratic_algorithm(int n){
for (int i=0; i<n; i++){
for(int j=0; j<n; j++) {
// do something for 1 second
}
}
}
public void another_O_quadratic_algorithm(int n) {
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// do something for 1 second
}
for (int k = 0; k < n; k++){
// do something for 1 second
}
for(int l = 0; l < n; l++){
// do something for 1 second
}
}
}
}2n, 5n을 모두 O(n)이라고 표현하는 것처럼, 3n^2, 5n^2도 n^2으로 표현함. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴식되기 때문에 이렇게 표기함.
O(2^n)
O(2^n)은 exponential complexity라고 부르며 Big-O라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가짐.
public int fibonacci(int n){
if (n <= 1){
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}재귀로 구현하는 피보나치 수열은 O(2^n)의 시간복잡도를 가진 대표적인 알고리즘.
