У меня есть n чисел между 0 и (n^4 - 1), что является самым быстрым способом, я могу сортировать их.Лучшее время работы для заказа n номеров
Конечно, nlogn тривиально, но я подумал о опции Radix Sort с базой n, и это будет линейное время, но я не уверен из-за -1.
Спасибо за помощь!
Я думаю, что вы недооцениваете эффективность Radix Sort. От Wikipedia:
Сложность сортировки Radix - это O (wn) для n ключей, которые являются целыми числами слова w. Иногда w представляется в виде константы, которая бы упрощала сортировку radix (при достаточно большом n), чем лучшие алгоритмы сортировки на основе сравнения, которые выполняют O (n log n) для сортировки n ключей. Однако, вообще говоря, w нельзя считать константой: если все n ключей различны, то w должно быть как минимум log n для машины с произвольным доступом, чтобы иметь возможность хранить их в памяти, что дает в лучшем случае временную сложность O (n log n).
Лично я бы использовал quicksort, выбрав intelligent pivot. Используя этот метод, вы можете достичь эффективности 1.188 n log n.
Если мы используем Radix Sort в базе n, мы получаем требуемую линейную временную сложность, значение -1 не имеет значения.
Мы будем представлять числа в базовой п:
Тогда мы получим: < = (журнал (основание п) (п^4 - 1)) * (п + п) < = 4 * (2n) < = O (n).
n для n чисел, другое n - это пробел цифр (переоценивается), а log n^4 - 1 меньше log n^4, который равен 4 в базе n. Общая линейная временная сложность.
Спасибо за помощь в любом случае! Если я сделал что-то неправильно, сообщите мне об этом!
Если бы было n^4, мы могли бы представить числа в базе n и достигнуть O (4n), следовательно, O (n) время, но -1 - моя проблема ... –
Я вижу вашу проблему сейчас. Я спрошу своих профессоров по алгоритму после урока завтра и посмотрю, что он говорит. – DrewB