[CS] 시간복잡도와 공간복잡도

 

코딩 테스트, 알고리즘 공부를 하면서 가장 먼저 마주치는 개념이

시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)이다.

테스트 케이스를 통과하는 것을 넘어 얼마나 빠르고 효율적으로 해결했는지가 중요하기 때문!

실제로 어려운 문제로 넘어갈수록 정답은 다 맞아도 시간 초과가 뜨는 경우가 허다하다

그것은 나의 경험

 

본격적인 알고리즘 스터디를 진행하기 전,

시간복잡도와 공간복잡도에 대해 한 번 더 정리하고자 한다.

 

 

1. 시간복잡도(Time Complexity)

시간복잡도는 입력 크기(n)에 따라 알고리즘의 실행 시간이 얼마나 증가하는지를 수치적으로 표현한 것.

쉽게 생각했을 때 최악의 경우 걸리는 연산 횟수의 증가율을 나타낸 것이다.

최악의 경우를 기준으로, 'Big-O 표기법'을 사용하여 나타낸다.

 

Big-O 표기법 규칙은 다음과 같다.

 

1. 항상 최악을 기준으로 표기

- 퀵 정렬의 경우 평균 시간은 O(n log n)이지만, 최악은 O(n^2)이다. 이때 표기는 O(n^2)!

 

2. 복수 시간복잡도가 생긴다면 '가장 큰 것'만 남긴다

- 1번 조건과 연계하여 만약 구현한 코드에서,

일부는 O(n^2)의 시간복잡도를, 일부는 O(log n)의 시간 복잡도를 가질 경우,

O(n^2 + log n) → O(n^2)과 같이 가장 큰 항만 남긴다.

 

 

내가 만약

for(int i=0; i<n; i++){
	for(int j=0; j<n; j++) {
     	//생략
    }
}

 

이런 코드를 작성했다면, 위 코드의 시간 복잡도는 O(n^2)이 된다

 

시간복잡도의 예시와 대표 알고리즘을 표로 나타내보자.

시간복잡도	의미	대표 알고리즘 예시
O(1)	상수 시간	배열의 index 접근, hashMap에서 key 조회
O(log n)	로그 시간	이진 탐색, 힙에서 삽입, 삭제
O(n)	선형 시간	배열/리스트 순회, 단일 반복문
O(n log n)	선형로그 시간	가장 빠른 비교 정렬 | Merge sort, Quick Sort 평균
O(n^2)	이중 반복문	Bubble Sort, BruteForce 조합 확인
O(2^n)	지수 시간	모든 부분집합 생성, 백트래킹 탐색 일부, DP를 활용한 외판원 문제
O(n!)	팩토리얼 시간	순열/조합 완전 탐색, 브루트 포스를 활용한 외판원 문제

 

 

 

시간 복잡도별 성능 차이를 나타낸 그래프이다

사실 입력 크기가 작을 때는 크게 영향이 없지만,

입력 크기가 조금만 커져도 O(n^2) 이상의 시간복잡도는 실행 시간이 급격하게 증가하기 때문에,

가능한 낮은 시간복잡도의 알고리즘으로 풀이하는 것이 매우 중요하다!

 

https://www.bigocheatsheet.com/

 

 

 

다음은 정렬 방법에 따른 시간복잡도

 

 

 

 

 

---

 

2. 시간복잡도를 계산하는 방법

그럼 내가 작성한 코드에 대해 시간복잡도를 어떻게 계산하여야 할까?

개인적으로 나는 log 단위의 시간복잡도를 계산하는 것이 처음에 어려웠다.

 

크게 다음과 같은 3가지를 주의해서 계산하면 된다.

 

- 반복문

- 재귀호출

- 자료구조 메서드

 

 

2-1. 반복문

시간복잡도	구조	계산 방법
O(n)	for(i=0; i<n; i++)	0~n까지 1번 순회
O(n^2)	이중 for문	0~n 내부에 0~n, 이중 반복문
O(log n)	while(n>0) {n /= 2};	절반씩 줄어듦
O(n log n)	n번 반복하며 내부에서 log n 연산	힙 정렬, 다익스트라

 

 

2-2. 재귀호출

- O(log n) : 재귀 함수 호출이 log n  깊이일 때

- O(n log n) : 재귀호출에서 매번 n만큼 분할할 때

 

재귀 호출 시 각 레벨에서 처리하는 데이터 양을 확인한 후,

트리 구조로 나타내면 쉽게 계산할 수 있다.

 

 

2-3. 자료구조 메서드

자료구조의 메서드의 경우 ArrayList, HashMap, TreeMap 등 각 메서드에서 시간복잡도를 꼭 확인해야 한다.

 

- ArrayList : O(1)- HashMap : 평균 O(1)- TreeMap : O(log n)- PriorityQueue : O(log n)

 

 

---

 

3. 공간복잡도(Space Complexity)

시간복잡도가 있다면, 공간복잡도도 있다!

 

공간복잡도는 알고리즘이 사용하는 메모리 양을 입력 크기 기준으로 분석하는 것이다

 

예를 들어 길이가 n인 배열이 있을 경우(int[] arr =new int[n];)

O(n) 공간을 사용하는 것이다.

만약 재귀 호출이 깊어질 경우 스택 공간도 고려해야 한다!

 

 

 

 

공간복잡도의 경우 알고리즘 자체에서는 시간복잡도보다 후순위 고려 사항으로 여겨지나,

복잡도가 커지면 메모리 초과가 발생하기에! 필요한 공간만 사용하도록 작성하는 것이 중요하다.

 

 

 

 

 

---

 

 

4. 같은 문제, 다른 시간 복잡도

 

만약, '정수 배열 arr이 주어졌을 때, 중복된 원소가 있는지 확인하라' 라는 문제가 있다고 하자.

이 문제를 풀 수 있는 방법은 아래와 같이 세 가지가 있다!

 

		// 브루트 포스 - 시간복잡도 : O(n^2) / 공간복잡도 : O(1)
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(arr[i]==arr[j]) return true;
            }
        }

        // 정렬 후 순회 - 시간복잡도 : O(n log n) 
        Arrays.sort(arr);
        for(int i=1; i<n; i++) {
            if(arr[i]==arr[i-1]) return true;
        }

        // HashSet 사용 - 시간복잡도 : O(n) / 공간복잡도 : O(n)
        Set<Integer> value = new HashSet<>();
        for(int a : arr) {
            if(!value.add(a)) return true;
        }

 

일반적으로(나도) 가장 많이 떠올리는 방법은 브루트 포스로,

이중 for문을 사용하여 전부 반복하는 것이다.

다만 이 경우에 최악의 경우 O(n^2)의 시간복잡도가 발생한다.

 

정렬 후 순회는 정렬에서 O(n log n), 순회는 O(n)이므로 O(n long n)의 시간복잡도를,

중복값을 허용하지 않는 HashSet의 경우 입력하면서 검사하기에 O(n)의 시간복잡도를 갖는다.

대신 HashSet의 경우 O(n)의 공간복잡도를 가지게 된다.

 

이처럼 같은 문제여도 다양한 풀이가 나올 수 있고, 

따라서 문제의 주어진 입력값의 크기, 시간 제한, 메모리 제한에 따라 적절히 풀이를 선택해야 한다.

 

 

---

 

 

제한된 시간과 메모리 내에서 문제를 해결하는 것이 진정한 알고리즘 풀이라고 생각한다!

코딩 테스트 준비를 본격적으로 진행하는 만큼,

작성한 코드의 시간복잡도와 공간복잡도를 꼭 계산해보는 습관을 가져야겠다

 

실제로 면접에서도 문제에 대한 코드 작성 > 시간 복잡도를 계산해봐라 > 더 줄일 수 있는 방법은 없느냐?

라는 흐름을 자주 가져가기에... 하나의 코드에 대해서도 다양한 방법의 접근이 필요하다!