CPython의 내장 타입 연산 시간 복잡도 총정리
Time complexity of operations on Python's built-in types
CPython의 내장 타입(list, tuple, dict, set, str 등)별 연산의 시간 복잡도를 Big O 표기법으로 정리한 문서입니다. 각 연산이 입력 크기에 따라 어떻게 실행 시간이 증가하는지 보여주며, 특히 list의 append는 O(1)이지만 중간 삽입/삭제는 O(n)이라는 점, dict와 set의 평균 O(1) 연산이 해시 충돌 시 O(n)으로 악화될 수 있다는 점 등을 강조합니다. 또한 tuple, frozenset, memoryview, range 등 불변 타입의 특성과 예외 사항도 다룹니다.
목록의 가장 큰 비용은 현재 할당 크기를 초과하여 늘어날 때(모든 요소를 이동해야 하므로) 또는 시작 부분 근처에서 삽입하거나 삭제할 때(그 뒤의 모든 요소를 이동해야 하므로) 발생합니다.
HN 토론
42- alexpotato
Dave Beazley는 Python 내장 타입을 데이터 분석 및 기타 빠른 작업에 사용하는 방법에 대한 훌륭한 강연을 했습니다 [0]. 메타적인 참고로, 저는 수년간 이러한 내장 타입들을 많이 사용해 왔지만, LLM 덕분에 점점 덜 사용하게 되었습니다. 그 비디오를 다시 보는 것은 마치 부시크래프트 전문가가 칼과 톱만으로 의자를 만드는 것을 보는 것과 거의 같았습니다...
- mwkaufma
O(n - k) 또는 O(len(l1) + len(l2))는 그냥 O(n) 아닌가요? 복잡도 분석과 사이클 계산 사이의 경계를 흐리게 하는 대신, 복잡도와 추정된 상대적 사이클 수를 별도의 측정치로 모두 출력하면 됩니다.
- StellarScience
Python은 유명하게도 해시 테이블을 중심으로 구축되었습니다. 그래서 몇 버전 전에 해시 테이블 구현을 개선했고, 전체 언어가 몇 퍼센트 빨라졌습니다. 그러나 O(log(N)) 복잡도를 가진 데이터 구조가 전혀 없다는 것은 놀랍습니다. 분명히 그것이 바람직한 사용 사례가 있을 텐데요?