파이썬 pop의 시간 복잡도에 대한 고찰(맨 뒤, 중간, 맨 앞 위치 비교 및 remove/del과의 비교)

Python pop() 함수의 시간 복잡도는 O(1)인가?

파이썬으로 원소를 제거하는 pop 함수의 시간 복잡도는 흔히 O(1)으로 알려져있지만

이 사항에는 맨 뒤 원소를 제거하는 상황이라는 조건이 반드시 필요합니다.

이번 글에서는 이에 대한 고찰을 간단한 예시 비교를 통하여 진행해보도록 하겠습니다.

 

 

1. 맨 뒤 위치 원소 pop : O(1)

pop 함수를 pop()처럼 default 인자로 사용할 경우 맨 뒤 위치(-1번 인덱스)가

자동으로 지정되어 사용되는데, 이 경우는 맨 뒤의 원소만 제거하고

기존 원소들은 그대로 놓아둘 수 있으므로 O(1)의 시간 복잡도가 맞습니다.

 

1천만개의 원소를 가진 리스트에서 1만번 pop을 진행시켜본다면

실제로 아래와 같이 약 0.002초 만에 완료된 모습을 볼 수 있습니다.

import time

x = [0] * (10 ** 7) # 1천만개 원소의 리스트

def pop_behind(x):
    for i in range(10 ** 4): # 1만회 반복
        x.pop(-1) # 맨 뒤 위치

start = time.time()

pop_behind(x)

end = time.time()
print(end - start) # 0.0020949840545654297

 

 

2. 중간 위치 원소 pop : O(N)

그러나, 중간 위치의 원소를 제거하게 된다면 remove 혹은 del을 통해 진행하면

제거된 원소 뒤에 위치한 모든 원소들을 전부 1칸씩 당겨와야하므로

이 경우 O(1)이 아닌 O(N)의 시간 복잡도를 나타내는데

pop 함수를 사용한 경우도 마찬가지의 원리가 적용됩니다.

 

실제로 위의 예시에서 가운데인 500만번째 원소를 pop으로 제거한

경우에는 아래와 같이 거의 40초에 가까운 시간이 소요되었습니다.

x = [0] * (10 ** 7) # 1천만개 원소의 리스트

def pop_middle(x):
    for i in range(10 ** 4): # 1만회 반복
        x.pop(5 * (10 ** 6)) # 중간 위치(500만번째 원소)

start = time.time()

pop_middle(x)

end = time.time()
print(end - start) # 39.848830223083496

 

반응형

 

3. 맨 앞 위치 원소 pop : O(N)

그렇다면 가장 앞의 위치의 원소를 pop을 통해 제거한 경우는 어떨까요?

맨 뒤의 원소를 제거한 경우와 비슷할 것으로 생각할 수도 있겠지만

오히려 모든 원소를 전부 1칸씩 당겨야하기에 가장 긴 시간이 소요됩니다.(당연히 O(N)입니다.)

 

따라서, 맨 앞의 위치를 더 자주 제거해야하는 경우에는 역순으로 뒤집어서

맨 뒤의 위치에서 pop을 진행해주는 것이 훨씬 좋을 수 있습니다.

 

같은 실험을 맨 앞 위치 원소에 대하여 진행한 결과 거의 80초의 시간이 걸렸습니다.

x = [0] * (10 ** 7) # 1천만개 원소의 리스트

def pop_front(x):
    for i in range(10 ** 4): # 1만회 반복
        x.pop(0) # 맨 앞 위치

start = time.time()

pop_front(x)

end = time.time()
print(end - start) # 80.09230709075928

 

 

참고 : remove, del과의 소요 시간 비교

제거하는 위치가 같은 경우에는 제거 후 원소들을 당겨오는 과정이

일어나는 원리가 비슷하게 적용되므로

실제 pop, remove, del 함수의 소요 시간은 거의 비슷합니다.

 

remove, del 함수에 대하여 맨 앞 원소에 대한 제거 실험을 진행한 결과는

아래와 같으며, 약 80초 근처로 비슷하다는 점을 확인할 수 있었습니다.

x = [0] * (10 ** 7) # 1천만개 원소의 리스트

def remove_front(x):
    for i in range(10 ** 4): # 1만회 반복
        x.remove(0) # 원소들이 전부 0이므로 맨 앞 위치 선택

def del_front(x):
    for i in range(10 ** 4): # 1만회 반복
        del x[0] # 맨 앞 위치

start = time.time()

remove_front(x)

end = time.time()
print(end - start) # 80.04945397377014

start = time.time()

del_front(x)

end = time.time()
print(end - start) # 79.59266376495361