Python 알고리즘 공부 (1: 복잡도에 대하여)

복잡도란 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간복잡도와 공간복잡도로 나누어진다.

 

 

• 시간복잡도: 알고리즘을 위해 필요한 연산의 횟수 (알고리즘이 얼마나 오래 걸리는가)
• 공간복잡도: 알고리즘을 위해 필요한 메모리의 양 (알고리즘이 얼마나 많은 메모리를 차지하는가)

 

 

동일한 기능을 수행하는 알고리즘이 있을 때 시간복잡도와 공간복잡도가 낮은 것이 더욱 좋은 것으로 일반적으로 해석될 수 있는 것이다. 또한, 효율적인 알고리즘을 사용한다고 했을 때 일반적으로 시간복잡도와 공간복잡도는 일종의 Trade-off 관계가 성립된다고 한다. 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있는 것이다. (이 때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매운 큰 경우가 종종 있다고 한다) 

 

 

 

일반적으로 알고리즘 문제에서 복잡도라고 말하면 이것은 시간복잡도를 뜻하는 것이다. 시간복잡도를 표현할 때는 Big-O 표기법이 사용된다. 이를 간단히 정의하면 가장 빠르게 증가하는 항만을 고려하는 표기법이라고 할 수 있다. (함수의 상한만을 나타내는 것) 

 

 

예를 들자면 N 개의 데이터를 모두 더해주는 알고리즘을 작성할 때, 연산 횟수는 데이터의 갯수 N 에 비례하는 것을 알 수 있다. 아래와 같은 코드의 시간 복잡도는 O(N) 이 되는 것이다. (summary 변수에 값을 대입, 출력하는 등의 연산은 N 이 커짐에 따라서 무시할 수 있을 정도로 영향이 작아지기에 N 만 고려하는 것)

 

 

 

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

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

 

 

 

 

한 번 더 예시를 살펴보자면 아래와 같은 코드는 O(N^2) 의 복잡도를 갖게 되는 것이다.

 

 

 

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

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

 

 

 

아래는 시간복잡도 표이며, 위에 위치할 수록 더욱 빠른 것이다.

 

 

 

시간복잡도 표

 

 

 

또 흔한 케이스는 아니라고 하지만, 실제 코딩 테스트에서 차수가 작은 항들을 완전히 무시하는 것은 좋지 않다고 한다. N 이 작을 때에는 상수의 영향력이 커지기 때문에, Big-O 표기법이 절대적인 표기법이 아니라는 것을 유념하고 있어야 한다.

 

 

 

공간복잡도를 표기할 때도 Big-O 표기법이 사용된다. 코딩테스트에서는 보통 메모리 사용량을 128~512 MB 로 제한하는데, 이를 지키기 위해서는 일반적인 경우 데이터의 개수가 1000 만 단위가 넘어가지 않도록 하면 된다. 

 

 

 

파이썬에서 시간복잡도를 직접 측정해보기 위해 time 모듈을 사용할 수 있다. 아래와 같은 형식으로 작성해준다.

 

 

 

import time
start_time = time.time()
end_time = time.time()
print(end_time-start_time)

 

 

 

 

 

Reference:

이것이 취업을 위한 코딩 테스트다