Can Sorting Be Faster Than O(n log n)? | Count Sort
0:00 · Watch on YouTube
이 클립은 계수 정렬(counting sort)이 O(n + k) 시간에 실행되는 것을 설명합니다. 여기서 *n*은 입력 요소의 개수이고 *k*는 값의 범위(최대 요소, 즉 계수 배열의 크기)입니다. k가 n에 비해 작으면 비용은 실질적으로 선형, O(n)입니다. 이는 더 긴 강의의 짧은 발췌이며 계수 정렬 절차가 시연된 직후에 시작됩니다.