입력 축 우선 고정
배열 길이인지, 정점 수와 간선 수인지에 따라 식이 달라진다.
복잡도는 반복 횟수와 보조 공간을 같이 세야 한다
이진 탐색처럼 빠른 연산이 보여도 그 뒤의 삽입, 복사, 재귀 프레임이 상한을 바꿀 수 있습니다. 코드 신호를 시간 비용과 공간 비용으로 나누면 오판이 줄어듭니다.
코드 신호눈에 보이는 줄
시간 비용반복마다 얼마인지
공간 비용추가 저장소 크기
입력 크기입력 크기와 연결
list.insert(pos, x)중간 삽입
O(N)뒤 원소 이동이 발생한다.
O(N)정렬 prefix 저장소가 커진다.
이진 탐색만으로 개선 아님전체는 여전히 O(N²)일 수 있다.
arr[:mid]슬라이스 복사
O(K)복사 길이만큼 시간이 든다.
O(K)새 배열이나 버퍼가 생긴다.
재귀와 합쳐 계산호출 전체에서 누적 비용을 본다.
dfs(node)재귀 호출
O(V+E)정점과 간선을 한 번씩 처리한다.
O(depth)호출 스택이 입력 깊이에 비례한다.
깊은 입력 주의시간은 맞아도 스택 한계가 먼저 올 수 있다.
set.add, in해시 연산
평균 O(1)충돌이 집중되면 느려질 수 있다.
O(N)버킷과 키 저장 공간을 쓴다.
평균/최악 분리입력 분포 가정을 문장으로 남긴다.
최대 메모리 순간 검토
정렬 버퍼와 슬라이스가 동시에 존재하면 순간 사용량이 커진다.
평균과 최악을 따로 적는다
해시와 퀵 정렬처럼 평균이 빠른 구조는 최악 입력을 별도 테스트한다.