👨⏰🐍 [Python] 시간복잡도 1

Memeory

• 1) 232 ⇒ 4GB**
• 2) 216 ⇒ 64MB**

Time

구체적인 성능은 플랫폼의 하드웨어에 따라서 달라지겠지만, 일반적으로 1초에 1억번 정도 계산할 수 있다고 가정하고 알고리즘의 시간 복잡도를 계산하면 된다. 즉, 어떤 문제의 시간 제한이 2초라면, 2억번 이하의 계산을 하는 알고리즘의 경우는 통과로 처리된다는 것이다.

시간 복잡도는 원래 데이터 개수에 따라서 달라지는 연산 횟수의 추이를 말한다. 하지만 많은 사람들은 편의상 데이터 개수와 연산 횟수를 동치로 간주하고 시간 복잡도를 계산하고 있다. 이러한 접근이 틀렸다고 보기 힘든 이유는 실전에서 정확하게 시간 복잡도를 계산하는 것이 불가능하기 때문이다. 애초에 시간 복잡도의 목적은 내가 세운 알고리즘의 대략적인 성능을 알아보기 위함이자, 문제 조건에 맞지 않는 경우의 수를 미리 처내기 위함이다. 이러한 관점에 따라서 어떤 문제의 시간 제한이 2초, 내가 세운 알고리즘이 O(N)의 시간복잡도를 갖는 상황을 가정해보자. 만약 문제에서 주어지는 데이터의 양이 2억개 이하라면 시간 초과에 걸리지 않고 통과할 것이다. 한편, 문제에서 주어지는 데이터의 양이 10억개라면, 선형 시간 복잡도 알고리즘으로는 다시 태어나도 절대 통과할 수 없다.

시간 복잡도	최대 데이터 길이 (1초)
O(log N)	1억**2
O(N)	1억
O(N**2)	1만
O(N log N)	30만
O(N**3)	500

이제 파이썬 내장 라이브러리의 시간 복잡도에 대해서 정리해보자. 파이썬의 가장 큰 장점은 타 언어 대비 내장 라이브러리가 많다는 점이다. 그래서 다른 언어로 구현할 때보다 내장 메서드를 사용하는 경우가 빈번하기 때문에 미리 해당 함수들의 시간 복잡도에 대해서 숙지하고 있어야 한다.

시간 복잡도	최대 데이터 길이 (1초)
O(1)	모든 인덱싱 활용 연산(자료구조 길이 등)
O(N)	전체 자료 구조 할당, 비교, 복사, 탐색
O(N log N)	정렬(sort(), sorted())

자료구조에 따른 내장 메서드가 너무 많아서, 최대한 일반화된 표현으로 작성했다. 여기서 한 가지 주목할 점은 자료구조 길이를 구하는 len()의 시간 복잡도가 상수 시간이라는 점이다. 파이썬 mutable 객체들은 모두 내부값이 변경될 것을 감안해 resize() 연산을 객체 내부 메서드에 가지고 있고, 자료구조 내부에 길이 정보값을 항상 내장하고 있다. 그래서 len(), __len__() 을 호출하면 자료구조를 순회하면서 길이를 세는게 아니라, 길이 정보값을 저장하고 있는 위치의 배열값을 반환한다. 따라서 상수 시간에 해결이 가능하다. 따라서 파이썬 mutable 객체의 크기는 우리 생각보다 좀 더 크다는 것을 명심하자.