정보 이론적 하한 편집하기 (부분)

==데이터 압축과 연산 하한==
어떤 데이터를 압축할 때, 정보 이론에서는 최소한의 비트 수를 사용해야 함을 제시한다. 예를 들어, n개의 상태를 구분하려면 최소 log₂(n) 비트가 필요하다. 이를 알고리즘 분석에 적용하면, 최소한의 연산 횟수를 도출할 수 있다.

예를 들어, 비교 기반 정렬의 하한은 Ω(n log n)이지만, 특정한 경우(예: 숫자가 제한된 범위 내에 있는 경우)에는 카운팅 정렬(Counting Sort)과 같은 알고리즘을 사용하여 O(n) 시간에 정렬할 수 있다.