파이썬 - 리스트, 집합, 딕셔너리 시간복잡도 정리

 

알고리즘을 풀면서 문제를 맞추어도 효율이 안좋은 경우가 종종 있다.

시간복잡도를 최대한 줄여 효율을 끌어올려야 겠다고 생각이 들어 시간복잡도를 정리해본다.

삽입(insert,pop), 제거(delete, remove) , 탐색(check ==,≠) 포함여부 확인( containment(in, not in))의 경우 List는 전부 O(N)이다. Set,Dict은 O(1)혹은 O(len)의 시간을 가지고 있다.

-> 삽입,삭제,탐색,포함여부 확인등의 문제는 list보다 set,dict을 사용하는게 효율면에서 뛰어나다고 생각한다.

 

List

 

Set

Dictionary