시간복잡도

[파이썬/Python] 리스트(list)의 메소드 시간 복잡도(Big-O) 정리

파이썬으로 코딩테스트를 진행하며 가장 많이 쓰는 기본 자료형은 리스트(list)와 문자열(string), 딕셔너리(dictionary), 집합(set) 정도이다. 기본 자료형을 벗어난 것 중 많이 쓰는 것은 collections 모듈의 Counter와 deque 정도가 있겠고, 아주 가끔 itertools 모듈의 permutations 혹은 combinations 정도를 쓰는 것 같다(사실 이 둘은 시간복잡도가 터져버리기 때문에 거의 안 쓴다). 약간 난이도가 있는 코딩테스트 문제들은 항상 시간복잡도와 공간복잡도에 대한 제약이 주어진다. 특히 시간복잡도에 대한 제약은 아주 중요하며, 이를 고려하기 위해서는 이용하는 자료형의 메소드 별 시간 복잡도를 알고 있어야 한다. 그래서 이번 기회에 정리를 해볼까 한..