알고리즘이 얼마나 빠르게 문제를 해결할 수 있을까요? 그리고 얼마나 적은 자원을 사용할 수 있을까요? 알고리즘의 효율적인 문제 해결은 매우 중요합니다. 이 성능을 비교하는 기준이 시간 복잡도와 공간 복잡도입니다. 이 글에서는 각 개념을 쉽게 설명하고, 다양한 알고리즘에서 이를 어떻게 평가할 수 있는지 알아보겠습니다.

⭐ 빅오 표기법 (Big-O Notation)

복잡도는 보통 빅오 표기법으로 표현합니다. 이는 알고리즘이 수행하는 연산의 증가 속도와 사용하는 메모리 공간이 입력 크기 n이 증가할 때 어떻게 변하는지를 나타냅니다.

*대부분은 빅오 표기법을 사용하여 최악의 성능을 표현하지만, 최선의 경우를 나타내는 빅 오메가 (Ω) 와 평균적인 경우를 나타내는 빅 세타 (Θ) 도 존재합니다.

1️⃣ 시간 복잡도 (Time Complexity)

알고리즘이 입력 크기(Input size)에 따라 얼마나 많은 시간이 걸리는지를 나타내는 척도입니다. 이는 알고리즘이 문제를 해결하는 데 소요되는 시간의 상한선을 나타냅니다.

✔️ 주요 유형

1) O(1) – 상수 시간(Constant Time)

- 입력 크기에 상관없이 항상 일정한 시간이 소요되는 경우

- 입력 크기에 관계없이 즉시 실행되므로 가장 빠른 성능을 보인다.

(ex. 배열에서 특정 인덱스에 있는 값을 읽는 연산)

int getFirstElement(int[] arr) {
	return arr[0]; // 배열의 첫 번째 요소를 반환하는 연산은 항상 일정한 시간이 걸리므로 O(1)
}

2) O(log n) – 로그 시간(Logarithmic Time)

- 입력 크기가 커질수록 실행 시간이 매우 느리게 증가하는 경우

- 대규모 데이터에서 매우 효율적이다.

(ex. 이진 탐색, 데이터 크기가 두 배로 늘어도 탐색 횟수는 1회만 더 필요)

// 이진탐색 
// 입력 배열이 정렬된 상태일때만 사용할 수 있으며, 이를 통해 탐색 범위를 절반으로 줄여가며 값을 찾음
int binarySearch(int[] arr, int target) {

	// low: 탐색 범위의 시작 인덱스, high: 탐색 범위의 끝 인덱스
    int low = 0, high = arr.length - 1;
    
    // low가 high보다 작거나 같을 때까지 반복
    while (low <= high) {
    
    	// 중간 인덱스를 계산 (소수점은 버려짐)
        int mid = (low + high) / 2;
        
        // 중간값이 목표 값과 같으면 인덱스 반환
        if (arr[mid] == target) return mid;
        
        // 중간값이 목표 값보다 작으면, 오른쪽 절반에서 탐색
        else if (arr[mid] < target) low = mid + 1;
        
        // 중간값이 목표 값보다 크면 왼쪽 절반에서 탐색
        else high = mid - 1;
    }
    
    // 목표 값을 찾지 못한 경우 -1 반환
    return -1;
}

🟢 이진 탐색과 로그의 관계

이진 탐색에서 배열의 크기가 절반씩 줄어들 때마다 한 번의 비교가 이루어진다.
(초기 배열의 크기가 n일 때) k번 절반으로 나누었을 때 크기가 1이 되는 값을 찾으려면, 다음과 같은 수식을 세울 수 있다.
n / 2^k = 1, 이 수식을 로그 형태로 변환하면 k = log₂(n)
여기서 k는 이진 탐색에서 값을 찾기 위해 필요한 비교 횟수 (반으로 나누는 횟수)
즉, log₂(n)은 이진 탐색에서 배열의 크기가 n일 때, 절반씩 줄여가며 값을 찾기 위해 필요한 비교 횟수

3) O(n) – 선형 시간(Linear Time)

- 입력 크기 n이 두 배로 증가하면,수행 시간도 두 배로 증가하는 경우

- 데이터의 양이 많아지면 그에 비례하여 시간이 증가하지만 대부분의 경우 적절히 빠르다.

(ex. 배열에서 모든 값을 순차적으로 검색하는 경우)

int sumArray(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i]; // 배열의 모든 요소를 더하는 연산은 모든 요소를 한 번씩 순회하므로 O(n)
    }
    return sum;
}

4) O(n log n) – 선형 로그 시간(Linearithmic Time)

- 시간 복잡도가 n과 log n의 곱으로 나타나는 경우

- 대부분의 효율적인 정렬 알고리즘에서 나타난다.

(ex. 병합 정렬 - 재귀적으로 배열을 반으로 나누고 다시 합침)

// 분할 과정: log(n)
void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 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) {
    // 병합 과정: O(n) (생략)
}

// 분할 과정의 시간 복잡도 * 병합 과정의 시간 복잡도 = nlog(n)

5) O(n²) – 이차 시간(Quadratic Time)

- 시간 복잡도가 입력 크기 n의 제곱에 비례하는 경우

- 중첩 반복문에서 주로 나타난다.

(ex. 버블 정렬 - 모든 요소를 두 번 반복하며 비교하고 정렬, 선택 정렬)

// 버블 정렬: 배열을 두 번 반복하므로 n^2
void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

6) O(2ⁿ) – 지수 시간(Exponential Time)

- 입력 크기 n이 커질수록 수행시간이 지수적으로 증가하는 경우

- 아주 비효율적이다.

(ex. 피보나치 수열을 재귀적으로 계산 - 같은 값을 여러 번 계산함)

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

7) O(n!) – 팩토리얼 시간(Factorial Time)

- 입력 크기 n이 증가할 때마다 시간 복잡도가 팩토리얼로 증가하는 경우

- 극도로 비효율적이다.

(ex. 순열을 계산하는 알고리즘 - n! 개의 경우의 수를 모두 탐색)

void generatePermutations(int[] arr, int start, int end) {
	
    // start와 end가 같으면, 배열의 한 가지 순열이 완성된 상태
    if (start == end) {
        // 순열 출력
        
    } else {
    	// 현재 위치(start)부터 마지막 위치(end)까지 순환
        for (int i = start; i <= end; i++) {
        	// 현재 위치(start)와 i 위치의 요소를 교환하여 새로운 순열 생성
            swap(arr, start, i);
            // 다음 위치(start + 1)에서 순열 생성 재귀 호출
            generatePermutations(arr, start + 1, end);
            // 교환한 요소를 다시 원상복구하여 다음 반복을 위한 준비
            swap(arr, start, i);
        }
    }
}

📌 정리

시간 복잡도	설명	예시 알고리즘	특성
O(1)	상수 시간	배열에서 특정 인덱스 접근	입력 크기와 무관
O(log n)	로그 시간	이진 탐색	입력 데이터가 정렬되어야 함
O(n)	선형 시간	배열 순차 탐색	입력 크기에 비례하여 성능 변화
O(n log n)	선형 로그 시간	병합 정렬, 퀵 정렬	대부분의 효율적인 정렬 알고리즘
O(n²)	이차 시간	버블 정렬, 선택 정렬	작은 데이터셋에 적합
O(2ⁿ)	지수 시간	피보나치 재귀적 계산	입력 크기가 커질수록 매우 비효율적
O(n!)	팩토리얼 시간	순열 생성	극도로 비효율적

2️⃣ 공간 복잡도

알고리즘이 문제를 해결하기 위해 사용하는 메모리의 양을 측정하는 척도입니다. 이는 프로그램이 실행되는 동안 추가적인 메모리 공간을 나타냅니다.

✔️ 주요 유형

1) O(1) – 상수 공간(Constant Time)

- 입력 크기와 무관하게 고정된 양의 메모리만 사용하는 경우

- 알고리즘에서 추가로 사용하는 메모리의 양이 일정하다.

(ex. 두 개의 변수만 사용)

int sum(int a, int b) {
    return a + b; // 이 경우 사용되는 메모리는 a와 b에 고정되어 있으므로 O(1)
}

2) O(log n) - 로그 공간(Logarithmic Space)

- 입력 크기가 n일 때, 로그에 비례하는 양의 메모리를 사용하는 경우

- 보통 재귀적 알고리즘에서 호출 스택의 깊이와 관련이 있다.

(ex. 재귀적 퀵 정렬)

int quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}
// 호출 스택의 깊이는 log(n)

3) O(n) - 선형 공간(Linear Space)

- 입력 크기 n에 비례하는 양의 메모리를 사용하는 경우

- 추가적인 데이터 구조를 사용하거나 재귀적으로 입력을 처리할 때 발생한다.

(ex. 병합 정렬)

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 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[] temp = new int[right - left + 1]; // 추가적인 배열 사용 -> O(n)
}

4) O(n log n) - 선형 로그 공간(Linearithmic Space)

- 입력 크기 n과 log(n)의 곱만큼 메모리를 사용하는 경우

- 보통 복잡한 분할 정복 알고리즘에서 나타난다.

(ex. log(n) 깊이의 재귀 호출이 발생하고 각 재귀에서 O(n)의 공간이 필요할 때)

5) O(n^2) - 이차 공간(Quadratic Space)

- 입력 크기 n의 제곱에 비례하는 메모리를 사용하는 경우

(ex. 2차원 배열)

int[][] createAdjacencyMatrix(int n) {
    int[][] matrix = new int[n][n]; // n * n 크기의 2차원 배열
    return matrix; // 공간 복잡도는 O(n^2)
}

6) O(2^n) - 지수 공간 (Exponential Space)

- 입력 크기 n에 대해 2의 지수만큼 메모리를 사용하는 경우

- 모든 가능한 경우의 수를 탐색하는 재귀적 알고리즘에서 발생한다.

(ex. 피보나치 수열의 재귀적 구현)

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2); // 공간 복잡도는 O(2^n)
}

7) O(n!) - 팩토리얼 공간 (Factorial Space)

- 입력 크기 n에 대해 팩토리얼에 비례하는 메모리를 사용하는 경우

- 매우 비효율적이다.

(ex. 순열 생성)

void generatePermutations(int[] arr, int start, int end) {
    if (start == end) {
        // 순열 출력
    } else {
        for (int i = start; i <= end; i++) {
            swap(arr, start, i);
            generatePermutations(arr, start + 1, end);
            swap(arr, start, i);
        }
    }
}

📌 정리

공간 복잡도	설명	예시 알고리즘	특성
O(1)	상수 공간	두 변수의 합 계산	고정된 메모리 사용
O(log n)	로그 공간	퀵 정렬 재귀 호출	재귀 깊이에 비례한 메모리 사용
O(n)	선형 공간	병합 정렬	추가적인 배열 사용
O(n log n)	선형 로그 공간	복잡한 분할 정복 문제	드물게 나타남
O(n²)	이차 공간	인접 행렬 생성	2차원 배열 사용
O(2^n)	지수 공간	피보나치 수열 재귀	지수적 메모리 사용
O(n!)	팩토리얼 공간	순열 생성 알고리즘	매우 비효율적

💡결론

시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 나타내고, 공간 복잡도는 문제를 해결하기 위해 사용하는 메모리의 양을 나타냅니다. 즉, 시간 복잡도는 문제를 얼마나 빨리 해결할 수 있는지에, 공간 복잡도는 얼마나 적은 메모리로 해결할 수 있는지에 중점을 둡니다.

각 유형의 시간 복잡도와 공간 복잡도를 이해하는 것은 알고리즘이 어떻게 동작하고 성능이 변화하는지를 예측하는 데 중요합니다. 이 지식을 바탕으로 문제의 특성에 맞는 알고리즘을 선택하면 보다 효율적인 해결책을 찾을 수 있습니다. 특히 입력 데이터가 매우 큰 경우나 제한된 메모리 환경에서는 복잡도의 이해가 성능 최적화의 핵심입니다.

또한, 시간 복잡도와 공간 복잡도는 서로 상충하는 관계에 있는 경우가 많습니다. 예를 들어, 시간을 절약하기 위해 추가적인 메모리를 사용하는 알고리즘이 있을 수 있고, 반대로 메모리를 절약하기 위해 시간이 더 많이 걸리는 알고리즘이 있을 수 있습니다. (✅ 실시간 처리가 필요한 경우에는 시간 복잡도를 더 중시해야 하며, 반대로 모바일 장치처럼 메모리가 제한적인 경우에는 공간 복잡도를 우선 고려하는 것이 좋음)

결국, 시간과 공간의 균형을 고려한 설계가 중요합니다. 이를 통해 문제의 특성과 환경에 맞는 최적의 알고리즘을 선택할 수 있고, 효율적이고 현실적인 문제 해결이 가능해집니다. 이 과정에서 시간 복잡도와 공간 복잡도의 이해는 필수적인 요소입니다. 😊

저작자표시 비영리 변경금지

[알고리즘] 시간 복잡도와 공간 복잡도

⭐ 빅오 표기법 (Big-O Notation)

1️⃣ 시간 복잡도 (Time Complexity)

✔️ 주요 유형

1) O(1) – 상수 시간(Constant Time)

2) O(log n) – 로그 시간(Logarithmic Time)

3) O(n) – 선형 시간(Linear Time)

4) O(n log n) – 선형 로그 시간(Linearithmic Time)

5) O(n²) – 이차 시간(Quadratic Time)

6) O(2ⁿ) – 지수 시간(Exponential Time)

7) O(n!) – 팩토리얼 시간(Factorial Time)

📌 정리

2️⃣ 공간 복잡도

✔️ 주요 유형

1) O(1) – 상수 공간(Constant Time)

2) O(log n) - 로그 공간(Logarithmic Space)

3) O(n) - 선형 공간(Linear Space)

4) O(n log n) - 선형 로그 공간(Linearithmic Space)

5) O(n^2) - 이차 공간(Quadratic Space)

6) O(2^n) - 지수 공간 (Exponential Space)

7) O(n!) - 팩토리얼 공간 (Factorial Space)

📌 정리

💡결론

티스토리툴바