 неэффективные сортировки, О(больше n^2) |
  |
| мисс_граффити |
 21.12.2006 1:37
Сообщение
#1
|
 просто человек  Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация:  55   |
Сдавала сегодня зачет по структурам и алгоритмам обработки данных... И зашел разговор об эффективности (точнее, о скорости работы) разных сортировок.
Почти во всех учебниках написано, что оценка любой сортировки попадает в О(n)-О(n^2) Я на википедии нашла упоминание о двух непрактичных сортировках: Алгоритм Bogosort — O(n × n!) — среднее время, неограниченный худший случай. Глупая сортировка (Stupid sort) — O(n^3) Поиск подробностей в гугле привел к получению горы мусора, к делу не относящейся... Кто-нибудь что-нибудь знает об этих (а может, еще каких-то) медленных сортировках? Откуда они взялись? Может, они выигрывают по какому-нибудь другому критерию? То есть зачем люди ищут способ ускорить сортировку (даже с усложнением алгоритма) - понятно, а зачем замедлять с усложнением? При желании же можно просто рэндомом перемешивать числа, пока они не упорядочатся... -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
   |
 
|
| volvo |
21.12.2006 12:37
Сообщение
#2
|
|
Гость |
Очень хорошее определение BogoSort:
Цитата(http://catb.org/~esr/jargon/html/B/bogo-sort.html) Bogo-sort is equivalent to repeatedly throwing a deck of cards in the air, picking them up at random, and then testing whether they are in order.  Так что, Цитата можно просто рэндомом перемешивать числа, пока они не упорядочатся... - это оно и есть...Кстати, вот еще немного информации: Inefficient sort algorithms |
|
|
|
| мисс_граффити |
21.12.2006 13:26
Сообщение
#3
|
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
спасибо!
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 12.06.2024 4:28 |