[Java/알고리즘] 시간 복잡도, 공간 복잡도, 빅오 표기법 이해하기

반응형

 
 
 

해당 글에서는 효율적인 알고리즘에 대한 설계 및 구현방법과 관련된 시간 복잡도와 공간 복잡도를 이용하며 이를 표기하는 빅오 표기법에 대해서 이해를 돕기 위해 작성한 글입니다.

 
 

1) 시간 복잡도(Time Complexity)

---

💡 시간 복잡도(Time Complexity)

- 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 ‘효율적인 알고리즘’을 나타내는 척도를 의미합니다.
- 즉, 입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는지에 따른 지표를 의미합니다.

- 시간 복잡도는 ‘빅오 표기법(Big-O notation)’를 통해 표현하며, ‘수치가 작을수록 효율적인 알고리즘’을 의미합니다.

 
 

2) 공간 복잡도(Space Complexity)

---

💡 공간 복잡도(Space Complexity)란?

- 알고리즘이 실행될 때 필요한 ‘메모리 공간의 양’을 의미합니다.
- 즉 알고리즘의 효율성을 판단하는 데 사용되며 일반적으로 메모리 사용량이 적을수록 더 효율적인 알고리즘이라고 할 수 있습니다.

- 공간 복잡도는 일반적으로 알고리즘의 시간 복잡도와 함께 고려되며 알고리즘이 실행되는 환경에 따라 달라질 수 있습니다. 예를 들어, 일부 알고리즘은 실행될 때 추가적인 메모리를 필요로 하지 않지만 다른 알고리즘은 입력 데이터의 양에 따라 필요한 메모리 공간이 증가할 수 있습니다.
- 따라서 알고리즘을 설계할때에는 시간 복잡도와 공간 복잡도를 함께 고려해야 합니다.

 
 

3) 빅오 표기법(Big-O notation)

---

💡 빅오 표기법(Big-O notation)이란?

- 알고리즘의 입력 크기에 대해 수행 시간이 어떤 방식으로 증가하는지를 표기하는 것으로 최악의 경우의 시간 복잡도를 의미합니다.
- 빅오 표기법을 통해 성능을 개선하거나 적절한 알고리즘을 선택할 수 있습니다.

 
 

[ 더 알아보기 ]

💡 최악의 경우의 시간 복잡도란?

- 알고리즘이 입력 크기에 따라 가장 오래 걸리는 경우를 의미합니다.
- 이를 분석함으로써 알고리즘을 설계할 때 최악의 성능을 예측하고 최악의 경우에도 어느 정도의 실행 속도를 보장함을 확인합니다.

 
 

1. 빅오 복잡성 차트(Big-O Complexity Chart)

---

 💡 빅오 표기법을 이용하여 알고리즘의 시간 복잡도를 분석하면, 입력 크기가 커질 때 어떤 알고리즘이 더 효율적인지 비교할 수 있다.

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

표기법	이름	시간 복잡도	설명	예시
O(1)	상수	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가집니다.	배열에서 원소 하나 찾기
O(logn)	로그	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가합니다.	이진 탐색 알고리즘
O(n)	선형	선형 시간	입력 크기와 비례하는 실행 시간을 가집니다.	선형 탐색 알고리즘
O(nlogn)	로그 선형	선형 로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가합니다.	병합 정렬, 힙 정렬 알고리즘
O(n^2)	이차	이차 시간	입력 크기의 제곱에 비례하는 실행 시간을 가집니다.	선택 정렬, 버블 정렬, 퀵 정렬 알고리즘
O(2^n)	지수	지수 시간	입력 크기의 지수에 비례하는 실행 시간을 가집니다.	부분집합
O(n!)	계승	팩토리얼 시간	입력 크기의 팩토리얼에 비례하는 실행 시간을 가집니다.	외판원 문제

 

2. 표기법 예시

---

2.1. O(1): 상수 시간 알고리즘

💡 배열에서 원소 하나를 찾는 예시입니다.

// O(1)
public static int getFirst(int[] nums) {
    return nums[0];
}

 
 

2.2. O(log n): 로그 시간 알고리즘

💡 이진 탐색 알고리즘의 예시입니다.

- 이는 입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가합니다. 이를 통해 정렬된 배열에서 특정 값을 찾을 때 유용하게 사용됩니다.

// O(log n)
public static int binarySearch(int[] nums, int target) {
    int left = 0, 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;
}

 
 
 

2.3. O(n) : 선형 시간 알고리즘

💡 해당 코드는 입력한 배열을 역순으로 만드는 함수를 구현한 예시입니다.

// O(n)
public static int[] reverse(int[] nums) {
    int[] reversed = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        reversed[nums.length - i - 1] = nums[i];
    }
    return reversed;
}

 
 
 

2.4. O(nlogn): 로그 선형 알고리즘

💡 해당 코드는 병합 정렬(merge sort)을 이용해 정렬하는 예시입니다.

// O(n log n)
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);
    }
}

 
 

2.5. O(n^2): 이차 시간 알고리즘

💡 해당 코드는 정수 배열을 선택 정렬(selection sort)을 이용해 정렬하는 예시입니다

// O(n^2)
public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIdx]) {
                minIdx = j;
            }
        }
        int tmp = nums[i];
        nums[i] = nums[minIdx];
        nums[minIdx] = tmp;
    }
}

 
 

2.6. O(2^n):지수 시간 알고리즘

💡 해당 코드는 피보나치수열을 구하는 예시입니다.

// O(2^n)
public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

[참고] 좀 더 자세히 이해하고 싶으시면 아래의 글을 참고하시면 도움이 됩니다

[Java/알고리즘] 피보나치의 수열(Fibonacci numbers) : 경우의 수

 
 

4) 정렬 알고리즘으로 바라본 시간/공간 복잡도

---

 

1. 시간 복잡도 관점

---

💡 시간 복잡도 관점에서는 ‘입력된 값’을 기반으로 ‘수행시간’에 따라서 나뉩니다.

- 정렬 알고리즘의 시간 복잡도를 통해서 이를 확인해 봅니다. 정렬 알고리즘에서 빅오 표기법은 최선, 평균, 최악의 경우로 세 가지로 나뉩니다.

- 최선의 경우는 입력이 이미 정렬되어 있을 때 등 최상의 상황에서의 시간 복잡도를 의미합니다.
- 평균의 경우는 모든 입력에 대해 평균적으로 소요되는 시간 복잡도를 의미합니다.
- 최악의 경우는 입력이 역순으로 정렬되어 있을 때 최악의 상황에서의 시간 복잡도를 의미합니다.

 

💡 일반적으로 알고리즘을 선택할 때는 최악의 경우를 보는 것이 좋습니다.

- 최악의 경우 시간 복잡도가 작은 알고리즘을 선택하면, 입력값이 매우 커졌을 때도 더 빠른 실행 시간을 보장할 수 있습니다.
- 또한 입력 크기가 작을 때는 차이가 미미하지만 크기가 커질수록 차이는 크게 벌어진다고 합니다.

 
 

2. 공간 복잡도 관점

---

💡 공간 복잡도 관점에서는 시간 복잡도와 함께 ‘메모리 공간의 양’에 따라서 나뉩니다.

- 공간 복잡도는 시간 복잡도와 다르게 최선, 평균, 최악의 경우에 대해서 다루는 것이 아닌 알고리즘을 수행하는 동안의 얼마나 많은 메모리를 사용하였는지에 대해서 다룹니다.

https://d2.naver.com/helloworld/0315536

 

💡 시간 복잡도와 동일하게 최악의 경우를 보는 것이 좋습니다.

- 최악의 경우 공간 복잡도가 작은 알고리즘을 선택하면 메모리 사용량이 낮은 알고리즘을 보장할 수 있습니다.

 
 
 

💡 [참고] 좀 더 다양한 알고리즘에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.

표기법	이름	시간 복잡도	설명	예시
O(1)	상수	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가집니다.	배열에서 원소 하나 찾기
O(logn)	로그	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가합니다.	이진 탐색 알고리즘
O(n)	선형	선형 시간	입력 크기와 비례하는 실행 시간을 가집니다.	선형 탐색 알고리즘
O(nlogn)	로그 선형	선형 로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가합니다.	병합 정렬, 힙 정렬 알고리즘
O(n^2)	이차	이차 시간	입력 크기의 제곱에 비례하는 실행 시간을 가집니다.	선택 정렬, 버블 정렬, 퀵 정렬 알고리즘
O(2^n)	지수	지수 시간	입력 크기의 지수에 비례하는 실행 시간을 가집니다.	부분집합
O(n!)	계승	팩토리얼 시간	입력 크기의 팩토리얼에 비례하는 실행 시간을 가집니다.	외판원 문제

 
 
 
 
 
 
 
 
 
오늘도 감사합니다. 😀