pop(0)와 pop()의 차이

list.pop([i])

목록에서 지정된 위치에서 항목을 제거하고 반환합니다. 인덱스를 지정하지 않으면 a.pop()이 리스트의 마지막 항목을 제거하고 반환합니다.

pop(0)의 시간 복잡도가 O(n)인 이유

먼저 pop()을 살펴보자. 위에서 말했듯이 pop()이 리스트의 마지막 항목을 제거하고 반환한다. 그렇기에 별다른 처리 과정이 필요하지 않기에 pop()의 시간 복잡도는 O(1)이다.

 

그렇다면 끝 원소가 아닌 그 외의 원소를 pop하는 것은 무엇이 다를까?

우선 python의 list는 배열로 설계되었음을 알아야 한다. 따라서 중간의 원소를 삭제하려면 해당 원소 다음 인덱스 원소들을 앞으로 당겨주어야 한다.

예를 들어, a= [1, 2, 3, 4] 란 list가 있을 때 원소 2를 지우고 싶으면 a.pop(1)을 실행하면 된다.(2의 원소 인덱스가 1이므로 a.pop(1)이다.) 만일 지우는 것만 실행된다면 list는 다음과 같은 형태가 될 것이다.

a = [1, , 3, 4]

2를 지운 공간이 비어버리는데 이는 우리가 원하는 결과와 다르다. 우리는 pop을 통해 원소가 제거되면 그만큼 list의 크기가 -1이 되길 원하고 삭제된 원소의 인덱스에 그 뒤의 원소들이 당겨지길 원한다.

 

위의 처리과정은 삭제한 원소 그 뒤의 남은 원소들을 당겨주어야하는 작업이기에 만약 첫번째 원소를 pop하는 경우 O(n-1)만큼 시간이 걸린다. 결론적으로 pop(i)의 최대 시간 복잡도는 O(n)이 된다.

 

참고

https://docs.python.org/3/tutorial/datastructures.html

5. Data Structures — Python 3.9.6 documentation