[이것이 코딩테스트다 with 파이썬] 1_복잡도

복잡도(complexcity)

알고리즘의 성능을 나타내는 척도

• 시간 복잡도(Time complexcity) : 특정한 크기의 입력에 대하여 알고리즘에 대하여 얼마나 오래 걸리는지 의미
• 공간 복잡도(Space complexcity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 의미

보통 시간 복잡도와 공간 복잡도는 거래 관계(trade off)이다. 연산 횟수를 줄이는 대신 메모리를 더 소모하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.

시간 복잡도(Time complexcity)

알고리즘 문제를 풀 때는 흔히 시간복잡도를 고려한다. 시간 복잡도를 표기할 때는 빅오(Big-O) 표기법을 사용한다.

• 빅오 표기법 간단 정의 : 빠르게 증가하는 항만 고려하는 표기법

arr = [3, 5, 1, 2, 4]
summary = 0

for x in arr:
    summary += x
print(summary)

위 예제에서는 데이터를 받아 차례로 5회 더해준다(N = 5). 이 때 연산 횟수는 N에 비례하는 것을 알 수 있다.
물론 summary 변수에 0을 더해주는 연산, summary 변수 값을 출력하는 부분도 있으나 연산 횟수는 N이 커짐에 따라서 무시할 수 있을 정도로 작아진다.
따라서 본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문 부분이므로 시간복잡도를 O(N)이라고 표기한다.

• 상수 시간 : 시간복잡도 - O(1) <- 연산 한번의 수행

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

• 이차 시간 : 시간복잡도 - O(N^2) <- N X N 연산 수행(모든 경우가 그런 것은 아님)

arr = [3, 5, 1, 2, 4]

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

모든 이중 반복문이 O(N^2)은 아니지만 만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간복잡도까지 고려 필요.

• 시간복잡도 표 : 위쪽에 있을 수록 빠름

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

• 빅오표기법의 한계
  연산횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘에 대해서 가정해보자.
  빅오 표기법에는 차수가 가장 큰 항만 남기기 때문에 O(N^3)으로 표기되지만, 실제로 N이 작을 때는 상수 값인 1,0000,000이 미치는 영향력이 매우 크다. 따라서 빅오표기법이 항상 절대적이지 않다는 것에는 유의하자.
• 시간 복잡도에서의 '연산'
  '연산'은 프로그래밍 언어에서 지원하는 사칙 연산, 기본 연산 등과 같은 기본 연산을 의미한다. 더하기 연산 뿐만 아니라 비교 연산 또한 한 번의 연산으로 취급한다.
• N이 1,000일 때의 연산 횟수

표기	연산 횟수
O(N)	1,000
O(NlogN)	10,000
O(N^2)	1,000,000
O(N^3)	1,000,000,000

• 알고리즘 풀이 전 시간 복잡도 암산
  예를 들어 데이터 개수 N이 알고리즘 1,000만개를 넘어가며 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야한다고 생각할 수 있다. 데이터 크기나 탐색범위가 100억이나 1,000억을 넘어가는 경우 이진탐색과 같이 O(logN)의 시간 복잡도를 갖는 알고리즘을 작성해야할 것이다.
• 시간 제한이 1초인 알고리즘의 경우
  • N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
  • N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

공간 복잡도

공간 복잡도 또한 빅오 표기법을 이용한다. 다만 시간 복잡도에서 1초라는 절대적인 제한이 있는 것처럼 메모리 사용량에도 절대적인 제한이 있다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.

• 예시 : 시간 제한 1초, 메모리 제한 128MB
• int a[1000] : 4KB
• int a[1000000] : 4MB
• INT a[2000][2000] : 16MB

코딩테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한한다. 다시 말해 데이터의 개수가 1,000만 단위가 넘지 않도록 알고리즘 설계를 해야한다는 의미다. 만약 리스트 크기가 1,000만 단위라면 자신이 알고리즘을 잘못 설계한 것일 가능성이 높다.

시간과 메모리 측정

수행시간 측정 소스코드

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

### 프로그램 소스코드 시작

### 프로그램 소스코드 끝

end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행시간 출력