파이썬 list 시간 복잡도 정리

list를 사용하는 일이 엄청 많기 때문에 list에서 자주 사용하는 내장 함수의 시간 복잡도를 정리해봤다.

시간 복잡도가 O(1)인 연산

• len(a)
• a.append(x)
• a.pop()

시간 복잡도가 O(k)인 연산

• a[i : j]

시간 복잡도가 O(n)인 연산

• x in a
• a.count(x)
• a.index(x)
• a.pop(0) => 시간 초과 나올 수 있으니, deque를 이용해서 popleft를 사용하면 O(1) 시간 복잡도로 맨 앞 요소를 뺄 수 있다.
• del a[x]
• min(a), max(a)
• a.reverse()

시간 복잡도가 O(nlogn)인 연산

• a.sort()

 

참고자료

Python list 연산에 따른 시간 복잡도