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 등 불변 타입의 특성과 예외 사항도 다룹니다.