По эффективности попыток и радикальной сортировки

Question

Сложность по времени сортировки по корням равна O (kn), где n - количество сортируемых ключей, а k - длина ключа.Аналогично, сложность времени для операций вставки, удаления и поиска в дереве составляет O (k).Однако при условии, что все элементы различны, не является ли k> = log (n)?Если это так, это будет означать, что асимптотическая временная сложность сортировки Radix равна O (nlogn), что равно быстродействию, а временные операции имеют временную сложность O (logn), равную сложности сбалансированного двоичного дерева поиска.Конечно, постоянные факторы могут существенно различаться, но асимптотические временные сложности не будут.Верно ли это, и если да, то у Radx-сортировки и попыток есть другие преимущества по сравнению с другими алгоритмами и структурами данных?

Редактировать:

Quicksort и его конкуренты выполняют O (nlogn) сравнения ;в худшем случае каждое сравнение будет занимать O (k) время (ключи отличаются только на последней проверенной цифре).Следовательно, эти алгоритмы занимают O (knlogn) время.По той же логике операции сбалансированного двоичного дерева поиска занимают время O (klogn).

Answer 1

Нотация Big O таким образом не используется, даже если k> = log n для радикальной сортировки, O (kn) означает, что ваше время обработки удвоится, если n удвоится и т. Д., Вот как вы должны использовать big-o нотации.

Одним из преимуществ сортировки по основанию является то, что в худшем случае это O (kn) (O быстрой сортировки (n ^ 2)), поэтому сортировка по основанию так или иначе более устойчива к вредоносному вводу, чем быстрая сортировка. Это также может быть очень быстро с точки зрения реальной производительности, если вы используете побитовые операции, степень 2 в качестве базовой и на месте сортировки msd-radix с сортировкой вставки для меньших массивов.

Тот же аргумент действителен для попыток, они устойчивы к злонамеренному вводу в том смысле, что в худшем случае вставка / поиск - O (k). Хеш-таблицы выполняют вставку / поиск в O (1), но с хешированием O (k) и в худшем случае вставкой / поиском O (N). Кроме того, попытки могут хранить строки более эффективно.

Проверка Атаки алгоритмической сложности

Answer 2

Асимптотическая временная сложность сортировки Radix равна O (NlogN), которая также является временной сложностью сортировки Qucik.Преимущество сортировки по Radix состоит в том, что ее лучшая, средняя и наихудшая производительность такие же, как и наихудшая производительность быстрой сортировки O (N ^ 2).Но это требует в два раза больше, как того требует быстрая сортировка.Таким образом, если сложность пространства не является проблемой, тогда сортировка по Radix является лучшим вариантом.