시간 복잡도
효율적인 알고리즘에 대한 고민
시간 복잡도(Time complexity) 는 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다.
알고리즘 문제를 풀 때 예상 입출력 케이스를 통과 했음을 확인해도, 정작 코드 제출을 하면 효율성에서 시간 초과로 통과하지 못하는 경우가 있다. 즉, 우리가 작성한 코드의 실행시간이 얼마나 걸리는지 알아야 한다.
여러가지 시간 복잡도 표기 방법
-
Big-O(빅-오) -> 상한 점근(최악의 경우)
최악의 경우 : 알고리즘의 실행 시간이 입력에 대해 가장 오래 걸리는 경우 -
Big-Ω(빅-오메가) -> 하한 점근(최선의 경우)
최선의 경우 : 알고리즘의 실행 시간이 입력에 대해 가장 짧게 걸리는 경우 -
Big-Θ(빅-세타) -> 위 둘의 평균
1. Big-O(빅-오)
시간복잡도는 최악을 기준으로 "빅오 표기법" 으로 판단하여 성능을 예측한다.
- O(1)
1. 일정한 복잡도(constant complexity)
2. 입력값이 증가하더라도 실행 시간이 늘어나지 않는다.
3. 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있음
- O(log N)
1. 로그 복잡도(logarithmic compleity)
2. 시간 복잡도는 O(1) < O(log N) < O(N) 순으로 크다.
3. 매번 탐색 범위의 중간값을 제시할 때마다 경우의 수가 절반씩 줄어듦.N이 커질수록 O(N)보다 O(1)에 더 가까워짐.
- O(N)
- 선형 복잡도(Linear complexity)
- 입력값이 증가함에 따라 실행 시간 또한 같은 비율로 증가
- 계수는 생략
- 입력값(N)이 커짐에 따라 계수의 의미가 퇴색되기 때문
- O(N²)
- 2차 복잡도(quadratic complexity)
- 입력값이 증가함에 따라 실행 시간이 N의 제곱수의 비율로 증가
- 2중 for 문법에서 보이는 시간 복잡도
1-1. 시간 복잡도의 빠른 순서
O(1) < O(log N) < O(N) < O(n log n) < O(N²)
- O(1) - 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리한다.
- O(log n) - 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
- O(n) - - 선형 시간 : 입력 크기와 비례하는 실행 시간을 가진다.
- O(n long n) - 선형 로그형 : 문제를 해결하기 위한 단계의 수가 N * (log2N)번 만큼의 수행 시간을 가진다.
- O(N²) - 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
1-2. O(1) 상수시간 예제코드
public staitc int getFirst(int[] nums){
return nums[0];
}배열에서 원소 하나를 찾습니다.
1-3. O(log n) 로그시간 예제코드
알고리즘의 각 단계에서 입력의 상당부분을 방문하지 않고 지나간다. ex)이진탐색 알고리즘
O(log n)은 밑이 2을 나타낸다. 그러나 Big-O 표기법에서 로그의 밑은 그다지 중요하지 않다. 즉 log의 밑은 의미에 크게 영향을 주지 않으므로 신경쓰지 않아도 된다.
// 이진탐색 알고리즘
public static int binarySearch(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}else if (nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}
1-4. O(n) 선형시간 예제코드
해당 코드는 병합정렬(merge sort)을 이용해 정렬하는 예시 입니다.
public static void mergeSort(int[] nums, int left, int right){
if(left < right){
int mid = left + (right - left) / 2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
merge(nums, left, mid, right);
}
}
1-5. O(N²) 이차시간 예제코드
해당 코드는 정수 배열을 선택 정렬(selection sort)을 이용해 정렬하는 예시 입니다.
public static void selectionSort(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
1-6. O(2^n) 지수시간 예제코드
해당 코드는 피보나치수열을 구하는 예시 입니다.
public static int fibonacci(int n){
if(n <= 1){
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}
노력