복잡도(Complexity)

 

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

 

복잡도를 측정함으로써 다음의 2가지를 계산할 수 있다.

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

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

 

시간 복잡도

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

 

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 간단히 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 함수의 상한만을 나타내는 것이다.

 

만약 소스코드가 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려해야 한다. 따라서 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다는 점을 기억해야 한다. 또, 최악의 경우 시간 복잡도와 평균 시간 복잡도에서 차이가 있을 수 있다. 가령 퀵 정렬의 평균 시간 복잡도는 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이 미치는 영향력이 매우 크다. 예를 들어 N = 10일 때, 3N^3 + 5N^2 + 1,000,000 = 1,003,500이므로 상수의 영향이 크다. 일반적인 코딩 테스트에서는 상수를 고려해야 하는 경우는 적지만, 이처럼 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억해야 한다. 

 

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

 

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

 

각기 다른 시간 복잡도의 연산 횟수가 N의 크기에 따라서 어떻게 분포되는지 확인해보자. 다음은 대략적인 연산 횟수를 비교한 표로, 시간 복잡도가 동일하더라도 실제 연산 횟수에서는 차이가 날 수 있다. 시간 복잡도가 O(NlogN)인 알고리즘은 매우 다양하다. 빅오 표기법으로 표시한 시간 복잡도가 같더라도 알고리즘 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번, 100,000번 등 실제 수행되는 연산 횟수는 다를 수 있다. (보통 시간 복잡도에서의 '연산'은 프로그래밍 언어에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다. 예를 들어 두 정수 a와 b를 더하는 더하기 연산뿐만 아니라, 두 정수 a와 b의 값을 비교하는 비교 연산 또한 한 번의 연산으로 취급한다.)

 

	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)인 알고리즘을 설계하면 문제를 풀 수 있다.

공간 복잡도

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

 

코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. (C/C++, JAVA에서는 배열이라는 단어를 사용하지만, 파이썬에서는 기본 자료형인 리스트가 배열의 역할을 포함한다.) 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 그렇다면 고전적인 프로그래밍 언어에서 정수형 자료형인 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)      # 수행 시간 출력

 

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

 

복잡도란 특정한 알고리즘이 계산적으로 얼마나 복잡한지를 나타내는 것이다. 동일한 기능을 수행하는 알고리즘이 2개(각각 A와 B) 있을 때 만약 A 알고리즘이 B보다 시간 복잡도가 더 높다면, A 알고리즘이 실행 시간 측면에서 성능이 더 낮다는 의미이다.

 

코딩 테스트에서 문제를 풀 때는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다. 일반적으로 알고리즘 문제 풀이에서의 복잡도는 계산 복잡도를 의미하는 경우가 많으며, '소스코드가 복잡하게 생겼다'와는 다른 말로 사용된다는 점을 기억해야 한다. 보통 '복잡도'란 시간 복잡도를 지칭하는 것이다.

 

 

 

 

 

[참고문헌]

나동빈, 2021, 「이것이 취업을 위한 코딩 테스트다 with 파이썬」, 한빛미디어.