파이썬 시간복잡도

최대시간이 1초일때 입력 데이터 수에 따른 시간 복잡도

파이썬으로 1초당 1억번의 연산을 한다고 가정

1,000개 : O(n2) 이하

10,000개 : O(n2) 미만

100,000개 : O(nlogn)이하

1,000,000개 : O(nlogn) 미만(가급적 O(n)을 사용하는 정도로)

 

파이썬 내장 함수들의 시간 복잡도

리스트(list)

O(1) : 조회, 값 할당, len()함수, list.append(), list.pop()

O(n) : 슬라이싱([a:b]), 리스트 + 리스트, list.pop(3), 1 in list, max(list) min(list), list.reverse()

O(nlogn): list.sort()

 

집합(set)

O(1): len(set), set.add(3), 3 in set, set.remove(3)

O(n): set(data), set1 | set2, set1 & set2, set1 - set2, set1 ^ set2, set1 == set2, set1 >= set2

 

딕셔너리(dictionary)

O(1): 조회, 값 할당, len()함수, dic.pop(2), dic.keys()

 

 

시간 복잡도를 줄이는 방법

1. input()함수 대신에 sys.stdin.readline()사용

2. 문자열 + 연산자 대신에 "".join() 사용

3. 조건문중 빨리 실행되는 것을 앞쪽에 배치하기