성능 경계

복잡도는 입력 N, 고유 키 U, 보존 후보 K를 분리해서 읽는다

같은 빈도 문제라도 전체 입력을 읽는 비용, 고유 키를 저장하는 비용, 상위 후보를 유지하는 비용이 서로 다릅니다.

N 원본 입력 크기 문자열, 배열, 스트림을 한 번 훑는 비용
U 정규화 후 고유 키 Map/Set에 남는 서로 다른 키 수
K 보존할 상위 후보 Top-K에서 힙이 유지하는 최대 크기
작업
핵심 상태
시간
공간
카운팅 + 중복
freq[key] + seen
O(N)
O(U)
Top-K 힙
freq + heap(K)
O(N + U log K)
O(U + K)
아나그램 판정
count vector / Map
O(N + M)
O(U)
N은 반드시 읽는다입력을 안 보고 빈도를 만들 수 없습니다.
U는 메모리 상한정규화 후 키가 많을수록 Map/Set이 커집니다.
K는 Top-K 절감 폭K가 작을수록 전체 정렬보다 유리합니다.