Нижняя граница для сортировки по сравнению - PullRequest
Новая
       17

Нижняя граница для сортировки по сравнению

6 голосов
/ 29 августа 2011

Сегодня я читал отличную статью от Джулиан Уокер о сортировке - Вечно запутался - Искусство сортировки , и одна вещь попалась на глаза. Я не совсем понимаю ту часть, где автор доказывает, что для сортировки по сравнению мы ограничены Ω ( N · log N ) нижней границей

Нижние границы не так очевидны. Наименьшая возможная граница для большинства алгоритмов сортировки - Ω ( N · log N ). Это связано с тем, что большинство алгоритмов сортировки используют сравнения элементов для определения относительного порядка элементов. Любой алгоритм, который сортирует по сравнению, будет иметь минимальную нижнюю границу Ω ( N · log N ), потому что дерево сравнения используется для выбора отсортированной перестановки. Дерево сравнения для трех чисел 1, 2 и 3 может быть легко построено: 

                         1 < 2

           1 < 3                       1 < 3

   2 < 3           3,1,2       2,1,3           2 < 3

1,2,3   1,3,2                            2,3,1     3,2,1

Обратите внимание, как каждый элемент сравнивается с каждым другим элементом, и что каждый путь приводит к действительной перестановке трех элементов. Высота дерева определяет нижнюю границу алгоритма сортировки. Поскольку для правильного алгоритма должно быть столько листов, сколько имеется перестановок, наименьшая возможная высота дерева сравнения равна log N !, , что эквивалентно Ω ( N · log N ) .

Кажется, это очень разумно до последней части (выделено жирным шрифтом), которую я не совсем понимаю - как записать N ! эквивалентно Ω ( N · log N ). Должно быть, я что-то пропускаю по своим курсам CopmSci и не могу получить последний переход. Я с нетерпением жду помощи с этим или какой-либо ссылки на другие доказательства того, что мы ограничены Ω ( N · log N ), если мы используем сортировку по сравнению.

Ответы [ 3 ]

9 голосов
/ 29 августа 2011

Вы ничего не пропустили из класса CompSci.То, что вы пропустили, был урок математики.Страница Википедии для приближения Стирлинга показывает, что log n!асимптотически n log n + члены более низкого порядка.

3 голосов
/ 29 августа 2011
  • N!
  • ∴ log N!
  • ∴ log N!
2 голосов
/ 30 августа 2011

Мое любимое доказательство этого очень элементарно.

N!= 1 * 2 * .. * N - 1 * N

Мы можем очень легко опустить нижнюю границу, представив, что первая половина этих продуктов не существует, а затем, что вторая половина всего лишь N/2.

(N / 2) ^ (N / 2) <= N! </p>

log ((N / 2) ^ (N / 2) = N / 2 * log (N / 2) = N / 2 * (log (N) - 1) = O (n log n)

Таким образом, даже если вы берете только вторую половину выражения и делаете вид, что все эти факторыне больше N / 2, вы все еще находитесь на территории O (n log n) для нижней границы, и это супер элементарно. Я могу убедить среднестатистического ученика в этом. Я не могу даже вывести формулу Стирлинга самостоятельно.

...