Я пытаюсь создать алгоритм, который может сортировать массив целых чисел за O (N) времени.
- Количество цифр во всех интергерсах равно N
- Каждый элемент имеет неизвестное количество цифр
- Алгоритм должен сортировать массив по времени O (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 всегда будет равно N.
Попытка доказательства
Base case: Array has 1 item.
T(N)= k*1. k=N = O(N)
Я не уверен, как сделать индуктивный шаг (если он даже требуется).