복잡도 Complexity : 시간 복잡도 Time Complexity, 공간 복잡도 Space Complexity

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저
Chapter 1 - 3. 복잡도 정리 내용

 

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

 

• 시간 복잡도 : 특정 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미. 알고리즘을 위해 필요한 연산의 횟수.
• 공간 복잡도 : 특정 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미. 알고리즘을 위해 필요한 메모리의 양.

동일 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다.

코딩 테스트에서 문제를 풀 때, 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다.

시간 복잡도

알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.

시간 복잡도를 표현할 때는 가장 빠르게 증가하는 항만을 고려하는 Big-O(빅오) 표기법을 사용한다.

Big-O 표기법은 함수의 상한만을 나타낸다.

O(N)

array = [3, 5, 1, 4, 2]	# 5개의 데이터. (N = 5)
summary = 0

# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in summary:
	summary += x

# 결과 출력
print(summary)	# 15

위의 소스코드에서는 5개의 데이터를 받아 차례로 5회 더해준다. (N = 5)

이 때 연산 횟수는 N에 비례함을 알 수 있다.

summary 변수에 0을 대입하는 연산도 있고, summary 변수의 값을 출력하는 부분도 있으나 이런 연산의 횟수는 상대적으로 N이 커짐에 따라 무시할 수 있을 정도로 작아질 것이다.
따라서 본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 부분이므로, 시간 복잡도를 O(N)이라고 표기한다.

O(1)

a = 5
b = 7
print(a + b)

위의 소스코드에서는 단순히 더하기 연산 한 번이 수행되고, 이는 상수 연산이기 때문에 시간 복잡도는 O(1)이다.
(a와 b에 값을 대입하는 대입 연산과 출력 함수는 무시)

O(N²)

array = [3, 5, 1, 2, 4]	# 5개의 데이터. N = 5

for i in array:
	for j in array:
    	temp = i * j
        print(temp)

위의 소스코드는 2중 반복문을 이용해 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문에,
데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N²)의 시간 복잡도를 가진다.

그러나 모든 2중 반복문의 시간 복잡도가 O(N²)은 아니다.
소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다.

따라서 소스코드를 정확히 분석한 후 시간 복잡도를 계산해야 한다.

 

평균 시간 복잡도와 최악의 경우 시간 복잡도가 다른 경우가 있다.

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하기 때문에, 최악의 경우의 시간 복잡도를 우선적으로 고려해야 한다.

 

아래는 자주 등장하는 시간 복잡도 표로, 위쪽에 있을수록 더 빠르다.

빅오 표기법	명칭
O(1)	상수 시간 (Constant time)
O(logN)	로그 시간 (Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ⁿ)	지수 시간

 

각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라 어떻게 분포되는지 확인해보자. (시간 복잡도에서의 연산은 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미)

아래는 대략적인 연산 횟수를 비교한 표로, Big-O 표기법으로 표시한 시간 복잡도가 동일하더라도 알고리즘의 내부 로직 및 차수가 낮은 항의 영향에 따라 실제 연산 횟수에서는 차이가 날 수 있다.

	N이 1,000일 때의 연산 횟수
O(N)	1,000
O(NlogN)	10,000
O(N²)	1,000,000
O(N³)	1,000,000,000

 

일반적으로 시간 제한이 1초인 문제를 풀 때에 대한 예시이다.

 

• N의 범위가 500: 시간 복잡도가 O(N³)인 알고리즘을 설계하면 문제 풀이 가능
• N의 범위가 2,000: 시간 복잡도가 O(N²)인 알고리즘을 설계하면 문제 풀이 가능
• N의 범위가 100,000: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제 풀이 가능
• N의 범위가 10,000,000: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제 풀이 가능

전체 복잡도

2가지 계산으로 구성된 알고리즘의 복잡도는 차원이 더 높은 쪽의 복잡도를 우선으로 한다.

따라서 O(f(n))과 O(g(n))의 동작을 연속으로 하는 경우, 복잡도는 일반적으로 다음과 같이 나타낸다.

O(f(n)) + O(g(n)) = O(max(f(n), g(n))

3가지 이상의 계산으로 구성된 알고리즘도 마찬가지이다.

O(1) + O(n) + O(n) + O(1) + O(n) + O(1) = O(max(1, n, n, 1, n, 1)) = O(n)

다시 말해 전체 복잡도는 차원이 가장 높은 복잡도를 선택하는 것이다.

공간 복잡도

공간 복잡도를 표기할 때에도 Big-O 표기법을 이용한다.

시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 공간 복잡도에서도 MB 단위로 제시된 메모리 사용량 기준에 대한 절대적인 제한이 있다.

 

코딩 테스트 문제는 대부분 리스트(배열)을 사용해 풀어야 하고, 다수의 데이터에 대힌 효율적인 처리를 요구한다.

고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보자.
(실제 컴퓨터 시스템에서 차지하는 메모리양은 컴파일러에 따라 조금씩 다르게 적용될 수 있다.)

• int a[1000] : 4KB
• int a[1000000] : 4MB
• int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한하므로, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다.

파이썬에는 int 자료형이 없으나, 대략 100만 개 이상의 데이터가 들어갈 수 있는 크기의 선언하는 경우는 적다. 따라서 리스트의 크기가 1,000만 단위 이상이라면 자신이 알고리즘을 잘못 설계한 것은 아닌지 고민해볼 것.

시간과 메모리 측정

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.

실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.

아래는 특정 프로그램의 수행 시간을 측정하는 소스코드의 예시로, 알고리즘 설계 후 시간 복잡도를 경험적으로 증명하고 싶을 때 주로 이용한다.

import time
start_time = time.time()	# 측정 시작

# 프로그램 소스코드
end_time = time.time()	# 측정 종료
print("time : ", end_time - start_time)	# 수행 시간 출력

---

이전에 간단한 입출력 문제를 풀 때 받았던 답변인데, 복잡도와 관련된 질의라 생각해 끝자락에 곁들이기 .. ✍️

나는 변수를 선언한 후 return 값에 해당 변수를 넣어 출력했는데, 변수 선언 없이 바로 return 값에 변수의 값을 주는게 낫다는 답변을 받았다. 

 

• 변수를 저장하기 위해선 비용이 듭니다. 비용이 늘면 시스템 성능의 저하가 올 수 있습니다.
• 또한 함수화 된 코드는 굳이 변수에 담지 않더라도 return 값으로 주면, 차후에 x = solution(someting) 같은 형태로 불러와서 사용이 가능하니, 재사용이 없는 함수 내 지역변수는 굳이 변수에 담지 않는 것을 추천합니다.

복잡도를 낮추는 방향으로 코드를 작성하자!