Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.135.183.89] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Известно, что у "быстрой" сортировки (QuickSort) среднее число сравнений пропорционально O(N*logN). Хотя с дополнением, что для некоторых случаев оно стремится к O(N^2). Но нигде не сказано, как получить такой пример!
Мой вопрос сводится к тому, как работают генераторы "плохих" тестов для сортировок. Можно ли написать программу, которая для некоторго метода сортировки с сложностью O(N*logN) выдает пример входных данных, при которых сложность становится O(N^2)? |
Сообщ.
#2
,
|
|
|
помоему ето ересь!! у быстрой сортировки не может быть больше чем O(N*logN)! наверное ето ещё у какоголибо метода
|
Сообщ.
#3
,
|
|||
|
2 wormball В быстрой сортировке массив разделяется на 2 части: элементы, меньшие заданного ключа - в одну, а большие - в другую. Потом эти части сортируются отдельно и склеиваются вместе. Фишка в том, что может получиться так, что на каждом шаге массив из N элементов будет делиться на 2 подмассива: из 1 элемента и из (N - 1) элемента. Так понадобится O(N) сортировок, что дает суммарное время O(N^2). O(N*logN) - это когда массив всегда делится на 2 примерно равные по размеру части. 2 Lucifer: Это серьезно, или тонкий юмор?! Вот, например, какой самый "плохой" тест для quicksort-а из Паскаля?
|
Сообщ.
#4
,
|
|
|
А причем здесь мама и папа?
PS: тема уходит в offtopic... |
Сообщ.
#5
,
|
|
|
ну тогда я думаю ето просто числа, расположенные в обратном порядке.
|
Сообщ.
#6
,
|
|
|
Тогда quicksort из раскидает за один проход!
Т.е. более N сравнений, IMHO, не будет. |
Сообщ.
#7
,
|
|
|
Да не обязательно в обратном... Просто в некоторых реализациях быстрой сортировки медиана (тот елемент, справа от которого и слева от которого...) выбирается случайным образом. Поетому генератором "плохих" входных последовательностей, на самом деле является математический объект, который фсе привыкли называть "демон". Ен точно знает, какая последовательность будет самой плохой. И неважно откуда, лишь бы выполнялось условие существования етой самой плохой последовательности.
Если медиана выбирается каким-то определенным образом, надо разместить елементы массива так, чтобы ета самая медиана не делила массив на части. (т.е., всегда оказывалась минимальным или максимальным елементом сортируемой подпоследовательности). |
Сообщ.
#8
,
|
|||
|
ты ещё скажи шайтан тогда наоборот: чтобы они уже были в правильном порядке рассортированы. тоесь она поймёт, что все последующие числа больше первого, и честно вызовет саму себя с массивом, меньшим на один элемент. кстати если они в обратном порядке, так тоже произойдёт. |
Сообщ.
#9
,
|
|
|
Не, тогда сложность логарифмической останется....
|
Сообщ.
#11
,
|
|||
|
почему?? |
Сообщ.
#12
,
|
|
|
Дык массив так и будет делиться пополам на каждой итерации...
|
Сообщ.
#13
,
|
|
|
в томто и дело, что так он будет делиться не пополам, а будет делиться на часть нулевого размера и часть, где будет почти весь массив. а потому она претерпит n самовызовов, и сложность будет n^2.
|
Сообщ.
#14
,
|
|
|
Да, можно в процедуру сортировки вставлять проверку "а не отсортирован ли уже массив?", и тогда некоторые часные случаи будут обрабатываться сами собой. Обычно для алгоритмов сортировки условие конца работы несколько проще.
|
Сообщ.
#15
,
|
|
|
ну ето будет имхо глупость, так ещё более замедлится. можно делить не первым, а средним элементом. а есь ещё помнится двухсторонняя быстрая сортировка.
|