시간 복잡도
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는 지 나타낸 것.
표기법에는 Big-O(빅-오), Big-Ω(빅-오메가), Big-θ(빅-세타) 들이 있지만 프로그램은 최악의 경우를 고려해야하므로 빅오표기법을 주로 많이 사용한다.
O(1)
입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
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입력값의 크기와 상관없이 index 주소로 가 바로 데이터를 가져오므로 시간에 영향을 주지 않는다.
O(n)
입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다.
public void another_O_n_algorithm(int n) {
for(int i = 0; i < n * 2; i++) {
// do something for 1 second
}
}위 코드의 경우 반복문이 돌아갈 때마다 실행 시간이 2초 씩 증가한다. 그러므로 O(2n)으로 표기하는게 맞지만 입력값이 커지면 커질수록 앞에 상수의 의미는 퇴색되기 때문에 O(n)으로 표기한다.
O(log n)
빅오표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
자료 구조 중 BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. 이렇게 BST 값 탐색 같은 로직을 가진 알고리즘은 O(log n)의 시간 복잡도를 가진다.
O(n^2)
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
이중 반복문이 그 예시이다.
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
}
}
}O(2^n)
빅오 표기법 중 가장 느린 시간 복잡도를 가진다.
예시로는 재귀로 표현한 피보나치 수열이 대표적으로 들 수 있다.
public int fibonacci(int n) {
if(n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci (n - 2);
}n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다.
탐욕 알고리즘
선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
예를 들어 거스름 돈이 870원이 나왔다면 동전을 가장 적게 사용하여 거스름 돈을 반환하는 방법은
500 원 동전 - 1 개
100 원 동전 - 3 개
50 원 동전 - 1 개
10 원 동전 - 2 개
총 7 개 일 것이다.
이 처럼 동전의 단위가 큰 수부터 순서대로 거슬러 주면 된다.
