Начнем с анализа каждого алгоритма самостоятельно и просмотра, если мы сможем определить, в каких случаях они будут выполняться в линейном времени.
Прежде всего, давайте посмотрим на подсчет сортировки. Алгоритм работает следующим образом:
- Найти наибольшее целое число для сортировки.
- Создайте массив с одним слотом на целое число для сортировки.
- Итерации по основному массиву, обновление второго массива с частотами каждого элемента.
- Построить отсортированный массив, заполнив выходной массив с соответствующим количеством копий каждого элемента.
Первый шаг может быть выполнен во времени O (n), итерируя по основному массиву. Предположим, что наибольшее значение в массиве - U. В этом случае второй шаг занимает время O (U), так как мы должны обнулить элементы массива. Третий шаг занимает время O (n). Заключительный шаг затем занимает время O (n + U), так как мы посещаем каждый элемент массива частот ровно один раз (O (U)) и суммируем n записей в выходной массив O (n). Это означает, что общая продолжительность работы O (n + U). Обратите внимание, что это зависит как от общего количества элементов, которые нужно сортировать (большие массивы занимают больше времени для сортировки), так и размеры элементов в массиве (для большего количества потребуется пропорционально большее время выполнения).
Если мы хотим, чтобы эта среда выполнения была O (n), нам нужно потребовать, чтобы U = O (n). Таким образом, мы будем иметь, что O (n + U) = O (n + n) = O (n). Это означает, что вам нужно, чтобы размер самого большого элемента в массиве возрастал примерно с той же скоростью, что и длина массива. Например, если вам гарантировано, что все элементы массива находятся в диапазоне 1 .. n, то для подсчета сортировки потребуется время O (n) для завершения. Неважно, как эти элементы распределяются в этом диапазоне.
Radix сортировать по существу работает, неоднократно делал разметку рода снова и снова, один раз для каждой цифры числа в массиве для сортировки.Основная идея сортировки radix - сохранить значение U по сравнению с предыдущим алгоритмом как можно более низким. Выбирая некоторую фиксированную базу, значение U ограничено некоторой константой. Например, если вы используете двоичную сортировку радиуса и каждый раз по одному бит, каждый элемент массива для сортировки по существу обрабатывается как 0 или как 1. Это означает, что каждый раунд сортировки по методу radix занимает время O (n) для завершения. Количество раундов, необходимых для сортировки всего массива, затем определяется числом цифр в наибольшем количестве в массиве, которое равно Θ (log U). Это означает, что общая продолжительность выполнения алгоритма заканчивается O (n log U). Заметим еще раз, что время выполнения зависит от количества элементов и от размера самого большого элемента в массиве.
Преимущество на этот раз, что лог-U растет гораздо, гораздо медленнее, чем U. Например, 2 составляет примерно от общего числа атомов во вселенной, но LG (2) = 300, что довольно мало.
Некоторые люди утверждают, что log U является константой на любом фиксированном компьютере. На 32-битном компьютере все целые числа - 32 бита (если вы не используете целые библиотеки произвольной точности, на которые мы сейчас будем игнорировать), а в 64-битной системе все целые числа - 64 бита. В первом случае log U = 32, а во втором log U = 64. Вы могли бы утверждать, что для фиксированной системы радиальная сортировка всегда принимает линейное время, так как время выполнения будет O (n). Однако константа варьируется от системы к системе. Если вы более теоретически настроены и хотите быть более точными, вы можете сказать, что сортировка радиуса выполняется в линейном времени до тех пор, пока log U = O (1), так как таким образом O (n log U) = O (n). Это означает, что если у вас есть постоянная верхняя граница количества бит в номере, вы гарантированно, что сортировка radix будет выполняться в линейном времени.
Алгоритм Ковш сортировки похож на Radix сортировки, за исключением того, что он распределяет элементы с использованием наиболее значащей цифры, а не значащей цифры. Это означает, что анализ почти такой же, как и раньше - до тех пор, пока log U = O (1), алгоритм работает в линейном времени.
Надеюсь, это поможет!
Radix, IIRC, всегда линейный, но постоянным фактором является количество бит в наибольшем целое. Таким образом, 32-разрядная сортировка счисления выполняется в 32 линейных проходах над данными. При N <2^32 вид N lg N типа mergesort будет быстрее. –
Когда вы говорите «линейное время», какой параметр вы пытаетесь быть линейным? Количество элементов? Число бит в наибольшем значении? Общее количество бит? – templatetypedef
@templatetypedef Я говорю о времени выполнения алгоритма. Поскольку судья утверждает, что да, все они линейны, но я хочу понять, когда будет оптимальный случай, время выполнения wise – ZAX