[Algorithm] Big-O Notation
알고리즘의 중요한 개념인 Big-O 표기법에 대해 정리하였습니다.
< Big-O Notation >
Big-O 표기법(Big-O Notation)은 알고리즘의 효율성을 표현하는 방법으로, 주로 입력 크기(n)에 따른 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 데 사용됩니다. 이를 통해 알고리즘이 실행될 때 얼마나 많은 리소스를 사용하는지 대략적으로 평가할 수 있습니다.
Big-O Notation에서 상수는 항상 무시합니다.
< 시간 복잡도(Time Complexity) >
시간 복잡도(Time Complexity)는 알고리즘이 완료되는 데 걸리는 시간을 나타내는 지표로, 주어진 입력 크기(n)에 대한 연산의 수를 평가합니다.
[ O(1) : 상수 시간 복잡도]
: 입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우입니다.
Ex)
function getFirstElement(arr) {
return arr[0];
}: 위 함수는 배열의 첫 번째 요소를 반환합니다. 배열의 크기와 무관하게 항상 일정한 시간이 걸리므로 O(1) 시간 복잡도를 가집니다.
[ O(log n): 로그 시간 복잡도 ]
: 입력 크기가 커질수록 시간 증가가 로그 함수와 같은 경우입니다
Ex)
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}: 이진 탐색은 정렬된 배열에서 값을 찾기 위해 중간 요소와 비교하여 범위를 절반씩 줄여 나갑니다. 따라서 O(log n) 시간 복잡도를 가집니다.
[ O(n): 선형 시간 복잡도 ]
: 입력 크기에 비례하여 시간이 증가하는 경우입니다.
Ex)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}: 위 함수는 배열에서 특정 값을 찾기 위해 모든 요소를 검사합니다. 배열의 크기가 커질수록 반복 횟수가 증가하므로 O(n) 시간 복잡도를 가집니다.
[ O(n log n): 로그 선형 시간 복잡도 ]
: 입력 크기 n과 로그 n의 곱에 비례하는 시간 증가입니다.
Ex)
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}: 병합 정렬은 배열을 반으로 나누어 각각 정렬한 후 병합합니다. 이 과정은 O(n log n) 시간 복잡도를 가집니다.
[ O(n²): 이차 시간 복잡도 ]
: 중첩된 반복문으로 인해 입력 크기의 제곱에 비례하여 시간이 증가하는 경우입니다.
Ex)
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}: 버블 정렬은 배열을 정렬하기 위해 중첩된 반복문을 사용하므로 O(n^2) 시간 복잡도를 가집니다.
[ O(2ⁿ): 지수 시간 복잡도 ]
: 입력 크기 n에 대해 지수적으로 시간이 증가하는 경우입니다.
Ex)
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}: 피보나치 수열을 재귀적으로 계산할 때, 동일한 부분 문제를 여러 번 계산하므로 O(2^n) 시간 복잡도를 가집니다.
[ O(n!): 팩토리얼 시간 복잡도 ]
: 입력 크기 의 팩토리얼에 비례하여 시간이 증가하는 경우입니다.
Ex)
function generatePermutations(arr) {
if (arr.length === 0) return [[]];
const result = [];
for (let i = 0; i < arr.length; i++) {
const rest = generatePermutations(arr.slice(0, i).concat(arr.slice(i + 1)));
for (let perm of rest) {
result.push([arr[i]].concat(perm));
}
}
return result;
}: 주어진 배열의 모든 가능한 순열을 생성하기 위해 각 요소에 대해 재귀적으로 순열을 계산하므로 O(n!) 시간 복잡도를 가집니다.
< 시간 복잡도(Time Complexity) >
공간 복잡도는 알고리즘이 완료되는 데 필요한 메모리 공간을 나타냅니다. 시간 복잡도와 마찬가지로 입력 크기 n에 대한 함수로 표현됩니다. 예를 들어, 배열을 사용하는 경우 O(n)의 공간 복잡도를 가질 수 있습니다.
Ex1 : 선형 검색(Linear Search)
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1- 시간 복잡도: O(n)
- 공간 복잡도: O(1)
Ex2 : 병합 정렬(Merge Sort)
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1- 시간 복잡도: O(n log n)
- 공간 복잡도: O(n)