[알고리즘] 복잡도 (시간 복잡도, 공간 복잡도)

복잡도는 알고리즘의 성능을 나타내는 척도로, 시간 복잡도와 공간 복잡도로 나눌 수 있습니다.

⏰ 시간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지

시간 복잡도를 통해 알고리즘을 위해 필요한 연산의 횟수를 계산할 수 있습니다.

알고리즘 문제를 풀 때 단순히 '복잡도' 라고 하는 경우엔 보통 시간 복잡도를 의미합니다.

시간 복잡도를 표현할 때에는 빅오(Big-O) 표기법을 사용합니다.
빅오 표기법을 간단하게 표현하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다. 함수의 상한만을 나타냅니다.
즉, 3N3 + 5N2 + 1000000 일 때 차수가 가장 큰 O(N3) 으로만 표기됩니다.

EX) N 개의 배열 값을 모두 더해 결과를 출력하는 프로그램

N 개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 만든다고 가정하겠습니다. 이런 경우 우리는 합계를 저장할 하나의 변수를 선언한 뒤에 모든 데이터를 하나씩 확인하며 그 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있습니다. 다음처럼요.

 	int arr[] = {1,2,3,4,5};
 	int sum = 0;

 	for (int i=0;i<arr.length;i++) {
 	 	sum += arr[i];
 	}
 	System.out.println(sum);

해당 코드에서는 N 의 개수에 따라서 연산 횟수가 달리지기 때문에
시간복잡도는 O(N) 입니다.

EX2) a+b 의 값을 출력하는 프로그램

int a = 5;
int b = 7;
System.out.println(a+b);

이번 코드는 a와 b 의 값을 단순히 더하는 코드로 굉장히 간단합니다.
여기선 단순 더하기 연산 한번만 수행되고, 이는 상수 연산 이기 때문에
시간 복잡도는 O(1) 입니다.

EX3) 2중 반복문

int arr[] = {1,2,3,4,5};

for (int i=0;i<arr.length;i++) {
    for(int j=0;j<arr.length;j++) {
        System.out.println(arr[i]*arr[j]);
    }
}

2중 반복문을 이용해 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 출력하는 코드입니다. N x N 만큼의 연산이 필요하다는 걸 유추할 수 있습니다. 그렇기 때문에
시간 복잡도는 O(N2) 입니다.

하지만, 모든 2중 반복문의 시간 복잡도가 O(N2) 가 아니기 때문에 소스 코드를 정확히 분석한 후 시간 복잡도를 계산해야한 다는 점을 기억해주세요.

시간 복잡도 표

빅오 표기법	명칭	N이 1,000일 때의 연산 횟수
O(1)	상수 시간 (Constant time)	1
O(logN)	로그 시간 (Log time)
O(N)	선형 시간	1,000
O(NlogN)	로그 선형 시간	10,000
O(n2)	이차 시간	1,000,000
O(n3)	삼차 시간	1,000,000,000
O(2n)	지수 시간

일반적으로 코딩 테스트 환경에서는 O(N3)을 넘어가면 문제 풀이에서 사용하기는 어렵습니다.

🏘 공간 복잡도

특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지

공간 복잡도를 통해 알고리즘을 위해 필요한 메모리의 양이 얼마인지 계산할 수 있습니다.

공간 복잡도에서도 표기할 때 시간 복잡도와 동일하게 빅오 표기법을 사용합니다.
코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512 MB 정도로 제한합니다.
배열을 기준으로 리스트 크기에 따른 메모리 사용량은 다음과 같습니다.

배열	메모리 사용량
int a[1000]	4KB
int a[1000000]	4MB
int a[2000][2000]	16MB

다시 말해 일반적인 경우 데이터 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야한다는 의미입니다.

레퍼런스

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드