2013-04-02 5 views
4

я изучаю следующие алгоритмы:В каких условиях эти сортировки не сравниваются с линейным временем?

  1. Счетные Сортировать
  2. Radix Сортировка
  3. Ковш Сортировать

Я знаю, что все три могут работать в линейном времени, в лучшем случае, но я у меня возникают проблемы с пониманием, когда происходят эти случаи, за исключением случая подсчета сортировки.

Вот мое понимание подсчета рода, и, как я хотел бы получить ответ на два других алгоритмов, если возможно:

Counting сортировки работает в линейном времени, когда есть не большие промежутки между информацией, которую вы хотите быть отсортирован. Например, 1, 10^5 и 545 и т. Д. Создавали бы большой массив и не были бы эффективными с использованием памяти и обхода, так что это было бы «худшим случаем» для использования сортировки, и поэтому наилучшим случаем было бы, когда промежутки небольшие.

Если бы кто-нибудь мог помочь мне понять условия для получения наилучших случаев для оснований и ведро, когда будет происходить линейное время, я был бы признателен.

+2

Radix, IIRC, всегда линейный, но постоянным фактором является количество бит в наибольшем целое. Таким образом, 32-разрядная сортировка счисления выполняется в 32 линейных проходах над данными. При N <2^32 вид N lg N типа mergesort будет быстрее. –

+0

Когда вы говорите «линейное время», какой параметр вы пытаетесь быть линейным? Количество элементов? Число бит в наибольшем значении? Общее количество бит? – templatetypedef

+0

@templatetypedef Я говорю о времени выполнения алгоритма. Поскольку судья утверждает, что да, все они линейны, но я хочу понять, когда будет оптимальный случай, время выполнения wise – ZAX

ответ

5

Начнем с анализа каждого алгоритма самостоятельно и просмотра, если мы сможем определить, в каких случаях они будут выполняться в линейном времени.

Прежде всего, давайте посмотрим на подсчет сортировки. Алгоритм работает следующим образом:

  • Найти наибольшее целое число для сортировки.
  • Создайте массив с одним слотом на целое число для сортировки.
  • Итерации по основному массиву, обновление второго массива с частотами каждого элемента.
  • Построить отсортированный массив, заполнив выходной массив с соответствующим количеством копий каждого элемента.

Первый шаг может быть выполнен во времени 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), алгоритм работает в линейном времени.


Надеюсь, это поможет!

+0

замечательный ответ! Спасибо большое! – ZAX