O (n) 시간에 n 개의 숫자가있는 0 ... n의 정수 배열 정렬

Question

O (N) 시간에 정수 배열을 정렬 할 수있는 알고리즘을 만들려고합니다.

• 는 intergers 모두의 자릿수는 각 요소의 숫자가 분배되는 방법에 관계없이, 알고리즘은 O (N)의 배열을 정렬한다
• 자릿수 알려지지 수 시간이 N
• 인

나는 O (N) 시간에 실행되는이 문제에 대한 해결 방법을 가지고 있습니다. 나는 그렇게하는 것으로 증명하려고하는 데 어려움을 겪고 있습니다.

Create a set of N buckets and add items to their corresponding bucket based off how 
many digits are in the integer -O(N) 

Radix sort each bucket, and then concatenate the buckets back together. 
Sum k=0 to N of O(k*n) 
k = Number of digits 
n = number of items with k digits 

내가 함께 온 솔루션은 그 ∑k*∑n 것입니다 내가 유도 단계를 수행하는 방법에 확실 해요

Base case: Array has 1 item. 
T(N)= k*1. k=N = O(N) 

증명 항상 동일한 N.

시도 (필요하다면).

Answer 1

다음 스크린 샷을 설명합니다