반응형
알고리즘을 좀 제대로 공부해보기 위해서 일요일이지만 공부 도저어언!
시간 복잡도 (amortized time complexity)
시간 복잡도는 알고리즘이 실행되는 동안 걸리는 시간을 입력 크기 n에 따라 측정하는 방식이다. 간단하게 말하면, "데이터 크기가 커질수록 알고리즘이 얼마나 느려지는지"를 나타낸다.
계산 과정
- 기본 연산 찾기: 알고리즘에서 가장 자주 반복되는 핵심 연산(덧셈, 비교, 곱셈 등)을 찾는다.
- 반복 횟수 세기: 이 기본 연산이 몇 번 실행되는지 n에 대해 식을 세운다.
- 가장 큰 영향 찾기: 계산 결과에서 입력 n이 커질수록 지배적인 항(가장 빠르게 증가하는 항)만 고려한다.
- 상수 제거: 상수는 무시한다. (예: 3n^2 + 5n + 10 -> O(n^2))
대표적인 종류
- O(1): 상수 시간. 입력 크기에 상관없이 실행 시간이 일정.
- 예: 배열의 특정 인덱스 접근.
- O(log n): 로그 시간. 데이터가 매번 절반으로 줄어들 때.
- 예: 이진 탐색.
- O(n): 선형 시간. 데이터 전체를 한 번씩 처리.
- 예: 배열 순회.
- O(n log n): 선형 로그 시간. 일반적인 정렬 알고리즘.
- 예: 병합 정렬, 퀵 정렬(평균).
- O(n^2): 제곱 시간. 중첩된 반복문.
- 예: 버블 정렬, 선택 정렬.
예제 문제 풀이
문제 1: 배열에서 최대값 찾기 - 주어진 정수 배열에서 가장 큰 숫자를 찾으세요.
알고리즘:
- 배열의 첫 번째 원소를 최대값으로 설정한다.
- 배열의 모든 원소를 한 번씩 비교하되, 더 큰 값이 나오면 최대값을 갱신한다.
int findMax(int[] arr) {
int max = arr[0]; // 첫 번째 값을 최대값으로 초기화
for (int i = 1; i < arr.length; i++) { // 나머지 원소 순회
if (arr[i] > max) {
max = arr[i]; // 최대값 갱신
}
}
return max;
}시간 복잡도: 배열의 크기가 n일때, n - 1번 비교 -> O(n)
설명:
배열: [3, 7, 2, 9, 5] (크기 n = 5)
- 처음에, 배열의 첫 번째 값 3을 현재 최대값으로 설정한다.
- 나머지 값들을 3과 차례대로 비교하며 최대값을 갱신한다.
- 7과 비교 -> 7이 더 크므로 7로 갱신.
- 2와 비교 -> 7이 더 크므로 그대로.
- 9와 비교 -> 9로 갱신
- 5와 비교 -> 9가 더 크므로 그대로.
- 총 4번 비교가 이루어졌다. n - 1 = 5 - 1 = 4.
왜 n - 1인가?
배열의 길이가 n일 때:
- 첫 번째 값은 "비교 없이" 최대값으로 설정되므로, 비교가 필요하지 않는다.
- 나머지 값 n - 1 개만 현재 최대값과 비교 한다.
시간 복잡도와 O(n)
- 배열의 크기가 매우 커진다고 생각해보자. n=100이면 99번 비교, n=1,000,000 이면 999,999번 비교.
- 이때, n−1이라는 구체적인 값 대신 대략적으로 n에 비례한다고 간주한다. 즉, O(n)으로 표현한다.(상수항 -1은 무시).
결론: 배열에서 최대값을 찾는 알고리즘은 모든 원소를 한 번씩 비교하므로 시간 복잡도는 O(n)입니다!
문제 2: 중첩된 반복문 - 2중 for문으로 n x n 행렬의 모든 원소를 출력한다.
void printMatrix(int[][] matrix) {
int n = matrix.length; // 행렬의 크기
for (int i = 0; i < n; i++) { // 바깥 루프
for (int j = 0; j < n; j++) { // 안쪽 루프
System.out.print(matrix[i][j] + " "); // 원소 출력
}
}
}시간 복잡도:
- 바깥 루프 n번 x 안쪽 루프 n번 n^2
- 따라서, O(n^2)
문제 3: 이진 탐색 - 정렬된 배열에서 특정 숫자를 이진 탐색으로 찾는다.
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 타겟 찾음
} else if (arr[mid] < target) {
left = mid + 1; // 오른쪽 탐색
} else {
right = mid - 1; // 왼쪽 탐색
}
}
return -1; // 타겟 없음
}시간 복잡도:
- 매번 탐색 범위가 절반으로 줄어듦
- 따라서 O(log n)
문제 4: 합병 정렬 - 배열을 오름차순으로 정렬하자(병합 정렬 사용)
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // 왼쪽 정렬
mergeSort(arr, mid + 1, right); // 오른쪽 정렬
merge(arr, left, mid, right); // 병합
}
}
void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}시간 복잡도:
- 분할: O(log n), 병합: O(n) -> O(n log n).
예제 - 시간 복잡도를 구해보자
def find_max_num(array):
for number in array: # (1) 바깥 for 루프
is_max_num = True
for compare_number in array: # (2) 안쪽 for 루프
if number < compare_number: # (3) 비교 연산 1번
is_max_num = False # (4) 대입 연산 1번
if is_max_num: # (5) 비교 연산 1번
return number- 바깥 for 루프
- for number in array: 는 배열의 크기 n에 따라 n번 반복 된다.
- 즉, 이 루프는 배열의 각 원소 number를 순차적으로 처리한다.
- 안쪽 for 루프
- for compare_number in array:는 바깥 로프의 각 number에 대해 배열의 모든 원소 compare number와 비교한다.
- 이 루프도 배열 크기 n에 따라 n번 반복된다.
- 비교 작업
- if number < compare_number: 는 안쪽 루프의 각 반복마다 한 번 실행된다. 비교 연산 1번.
- 조건이 참일 경우, 대입 연산 1번.
- 따라서 총 비교 횟수는 n x n = n^2 이다.
- 바깥 is is_max_num
- 바깥 루프에서 매번 실행: 비교 연산 1번
시간 복잡도 계산
- 바깥 루프: n번 반복.
- 안쪽 루프: 바깥 루프의 각 반복마다 n번 반복.
- 안쪽 if 까지: N번 반복 x N번 반복 x (비교연산 1번 + 대입연산 1번) = n^2 x 2
- 바깥 루프에서 n번 반복 x (비교 연산 1번) = n
- 따라서 전체 연산 횟수는 n^2 * 2 + n 시간 복잡도는 O(n^2) 이다.
어렵다^^
반응형
'Study > Algorithm' 카테고리의 다른 글
| [Algorithm] BFS, DFS, 이진 탐색, 순차 탐색 등 알아보자... (0) | 2025.01.09 |
|---|
댓글