복잡도

복잡도

 

복잡도(complexity)는 알고리즘의 성능을 나타내는 척도다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

• 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
• 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양

 

효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(trade-off)가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다.

---

 

 

시간 복잡도

 

알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다. '시간 제한'이라면 문제를 푸는 시간을 정한 듯하지만, 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 그래서 해당 시간 안에 동작하는 프로그램을 작성해야 정답 판정을 받을 수 있으며, 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 Time Limit Exceeded라는 메시지와 함께 오답으로 처리된다.

 

시간 복잡도를 표현할 때는 빅오(Big-o) 표기법을 사용한다. 엄밀한 정의는 아니지만, 빅오 표기법을 간단희 정의하자먼 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 다시 말해 함수의 상한만을 나타낸다. 예를 들어 N개의 데이터가 있을 때, 모든 데이터의 값을 더한 결과를 출력하는 프로그램을 생각해보자. 이때 우리는 합계를 저장할 하나의 변수를 선언한 뒤에 모든 데이터를 하나씩 확인하여 그 값을 합계 변수에 더해주는 식으로 알고리즘을 작성할 수 있다. 

 

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

 

array = [3, 5, 1, 2, 4] #5개의 데이터
summary = 0 #합계를 저장할 변수

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

#결과 출력
print(summary)

#실행 결과
15

 

 

 

다음 소스코드는 어떤 시간 복잡도를 가질까?

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

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

 

 

 

다음 소스코드는 어떤 시간 복잡도를 가질까?

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

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

 

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

하지만 모든 2중 반복문의 시간복잡도가 O(N^2)은 아니다. 만약 소스코드가 내부적으로 다름 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다. 따라서 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다.

 

(퀵 정렬의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 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,000,000이 미치는 영향력이 매우 크다. 일반적인 코딩 테스트에서는 상수를 고려해야 하는 경우는 적지만, 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억하자.

 

더불어 컴퓨터 과학에서는 특정한 알고리즘의 시간 복잡도가 O(N^k)일 때(k는 상수 값을 가진다.), 이를 '다항 시간에 동작하는 알고리즘'이라고 말한다. 이차 시간, 삼차 시간 등이 모두 다항시간에 해당한다. 이론적으로는 특정한 문제가 이러한 다항 시간 알고리즘으로 풀 수 있을 때 해당 알고리즘은 풀 만한 알고리즘으로 분류 되지만, 실제로는 그렇지 않다.

 

일반적으로 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다. 왜냐하면 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 c언어를 기준으로 통상 1초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸릴 수 있다. 특히 파이썬은 더욱 오래 걸리며, 코딩 테스트 문제에서 시간 제한은 1~5초가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정을 받을 수 있다.

 

	N이 1,000일 때의 연산 횟수
O(N)	1,000
O(NlogN)	10,000
O(N^2)	1,000,000
O(N^3)	1,000,000,000

 

 

시간 복잡도 분석은 문제 풀이의 핵심이다. 알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 한다. 문제의 조건을 먼저 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있기 때문이다. 

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

 

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000인 경우 : 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다. 

---

공간 복잡도

 

공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다. 즉, 공간 복잡도 또한 O(NlogN), O(N^2) 등으로 표현한다. 다만, 앞서 시간 복잡도에서 1초라는 절대적인 제한이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다. 쉽게 말해 코딩 테스트 문제에서 보이는 '시간 제한1초 메모리 제한 128MB'와 같은 문장은 시간-공간 복잡도를 함께 제한하기 위해 명시하는 것이다.

 

코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 그렇다면 고전적인 프로그래밍 언어에서 정수형 자료형인 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) #수행 시간 출력

수행 시간 측정 소스코드의 형태는 일반적으로 위와 같다. 보통 어떤 알고리즘을 설계한 뒤에 시간 복잡도를 경험적으로 증명하고 싶을 때는 위와 같은 형태의 코드를 자주 이용한다.

 

예를 들어 '선택 정렬'과 '파이썬의 기본 정렬 라이브러리'의 속도를 비교할 때는 아래의 코드와 같이 작성하면 된다. 선택 정렬을 사용할 때 최악의 경우 시간 복잡도가 O(N^2)이며, 파이썬의 기본 정렬 라이브러리는 최악의 경우 시간 복잡도 O(NlogN)을 보장하여 상대적으로 빠르다. 다음 소스코드의 실행 결과가 그러한 성능 차이를 직접적으로 보여준다.

 

from random import randint
import time

#배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
    array.append(randint(1,100))

#선택 정렬 프로그램 성능 측정
start_time = time.time()

#선택 정렬 프로그램 소스코드
for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] #스와프

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

#배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
    array.append(randint(1,100)) #1부터 100 사이의 랜덤한 정수

#기본 정렬 라이브러리 성능 측정
start_time = time.time()

#기본 정렬 라이브러리 사용
array.sort()

end_time = time.time()
print("기본 정렬 라이브러리 성능 측정 : ", end_time - start_time) #수행 시간 출력

선택 정렬 성능 측정 : 5.667983055114746
기본 정렬 라이브러리 성능 측정 :  0.0009834766387939453

선택 정렬은 5초 넘게 걸렸고, 기본 정렬은 1초도 채 걸리지 않을 만큼 짧은 시간이 걸렸다. 이처럼 자신이 설계한 알고리즘의 성능을 실제로 확인하기 위해서, 시간 측정 라이브러리를 사용해보는 습관을 기르는 것이 좋다.