IPB
ЛогинПароль:

> неэффективные сортировки, О(больше n^2)
сообщение
Сообщение #1


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Сдавала сегодня зачет по структурам и алгоритмам обработки данных... И зашел разговор об эффективности (точнее, о скорости работы) разных сортировок.
Почти во всех учебниках написано, что оценка любой сортировки попадает в О(n)-О(n^2)
Я на википедии нашла упоминание о двух непрактичных сортировках:
Алгоритм Bogosort — O(n × n!) — среднее время, неограниченный худший случай.
Глупая сортировка (Stupid sort) — O(n^3)

Поиск подробностей в гугле привел к получению горы мусора, к делу не относящейся...
Кто-нибудь что-нибудь знает об этих (а может, еще каких-то) медленных сортировках? Откуда они взялись? Может, они выигрывают по какому-нибудь другому критерию?
То есть зачем люди ищут способ ускорить сортировку (даже с усложнением алгоритма) - понятно, а зачем замедлять с усложнением?
При желании же можно просто рэндомом перемешивать числа, пока они не упорядочатся...


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.11.2021 21:57
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name