Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 [3]  Все   Вниз
  Печать  
Автор Тема: Заметки о рекурсии  (Прочитано 48772 раз)
0 Пользователей и 1 Гость смотрят эту тему.
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #60 : 31-05-2004 11:45 » 

NetRaider, есть алгоритмы сортировки, в которых вообще нет сравнений.

Пример -- сортировка целых чисел массивом.  Проводится в предположениях, что числа, которые надо отсортировать, в диапазоне [p, q]

Тогда заводится битовый массив размером (q-p+1), все биты обнулены.

Сортировка.  Перебираем целые числа одно за другим.  Встретив число n выставляем бит (флаг) в ячейке с номером (n-p) (нумеруем битовый массив с нуля)

После того, как все числа пройдены, в битовом массиве хранится информация о том, какие числа были встречены.  Проходим массив слева направо, для единичек (флаг поднят) включаем в результат сортировки соответствующее число.

Можно рассмотреть вместо битов счётчики.  Для каждого числа в исходном массиве считаем, сколько раз число встретилось, затем столько раз это число сбрасываем в результат

Как видно, вообще ни одного сравнения не производится.

Так что минимальное число сравнений -- 0.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #61 : 31-05-2004 11:49 » 

Alf, минимальный максимум строится так.

Сначала по каким-то соображениям строится семейство максимумов.  Например, в теории принятия решений для каждого альтернативного решения, допустимого в данной ситуации, определяется максимальный возможный ущерб.  В полученном множестве ищется минимум.  Результат -- минимальный максимум.

Правда, не совсем понятно, какое отношение эта конструкция имеет к сортировке?  Максимумы чего строятся на первом шаге?
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Alf
Гость
« Ответ #62 : 31-05-2004 12:30 » 

npak, минимаксы из теории принятия решений, теории игр (AB-деревья и др.) и тому подобные к теории NetRaider'а я тут никоим боком прилепить не сумел. Из каких альтернатив мы выбираем минимакс?

Поэтому подумал уж было, что и правда в теории прошляпил. В данном применении "минимальный максимум" мне показался просто бессмысленным сочетанием слов.

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

Традиционно при анализе алгоритмов сортировке определяется минимальное число сравнений (если нам повезло и данные изначально расположились максимально благоприятным для данного алгоритма образом), максимальное (при неблагоприятном начальном положении) и среднее (наиболее вероятное в общем случае) число сравнений и пересылок. Никаких "максимальных минимумов", "минимальных максимумов" и прочих экзотических функций доселе встречать не доводилось.
Записан
NetRaider
Гость
« Ответ #63 : 01-06-2004 00:43 » 

Цитата: Alf
Боюсь, что в информатике (как и в математике в целом) все весьма конкретно: доказательство относится к данной теореме, формула - к данному алгоритму и т.д. Ожидать появление универсальной формулы для всех алгоритмов поиска столь же вероятно, как и единого доказательства всех теорем разом, в том числе и еще не сформулированных.


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

Цитата

Да и в чем тогда необходимость изобретения разных алгоритмов, если метрики у них все равно одинаковы?


Это зависит от природы используемых данных и начальных условий(приминительно к алгоритмам сортировки). Например, нужно отсортировать массив объектов; берем быструю сортировку - быстродействие в худшем случае O(n^2), для любых объектов подойдет. Но если исходный массив состоит из чисел, время можно улучшить до O(n).


Цитата

Цитата
...Но минимальный максимум - 3.

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


Ок, берем несколько алгоритмов сортировки(рассматриваем кол-во k(n)сравнений в наихудшем случае, т.е. максимумы)
1) быстрая - k(n) = n^2
2) сортировка простым выбором - k(n) = 1/2(n^2-n)
3) для наглядности можно взять какой-нибудь 'страшный'  алгоритм -   k(n) = n^3
4) 'несуществующий' алгоритм -  пусть нам известна формула для минимального кол-ва сравнений(о которой я говорил) и алгоритм ее реализующий.  k(n) = c(n) = Не понял

Еще раз напомню что k(n) - гарантированное кол-во сравнений, при помощи которых можно выполнить сортировку(в частных случаях возможно потребуется меньше).

Пусть дан массив из 5 элементов, тогда используя вышеперечисленные алгоритмы потребуется сравнений(максимум)

1) - 25
2) - 10
3) - 125
4) формула неизвестна, но 5 объектов можно отсортировать за 7 сревнений.

таким образом минимальный из максимумов получится, если использовать алгоритм (4).

P.S. Неудачно выбрал термин...
Записан
NetRaider
Гость
« Ответ #64 : 01-06-2004 00:50 » 

Цитата: npak
NetRaider, есть алгоритмы сортировки, в которых вообще нет сравнений.


Это мне известно. Все вышесказанное применимо для множеств с определенными отношениями порядка ('>', '<', и возможно '=') и никакими другими. Если доступны другие операции над элементами множества, тогда сортировка вырождается в частные случаи(например для чисел).
Записан
Alf
Гость
« Ответ #65 : 01-08-2004 19:30 » 

Тема рекурсии возрождается.

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

Обсуждаем здесь или делаем новую тему?
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #66 : 09-08-2004 19:23 » 

Alf, я начал тему здесь:
http://forum.shelek.ru/index.php/topic,4189.0.html
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #67 : 22-10-2005 23:31 » 

Вот здесь небольшая ошибка
http://club.shelek.ru/viewart.php?id=184
Цитата
, в которых применение рекурсии просто расточительно и е выдерживает никакой конкуренции с рекурсией.
В принципе всё понятно. Но лучше исправить.
Цитата
, в которых применение рекурсии просто расточительно и не выдерживает никакой конкуренции с итерацией.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #68 : 23-10-2005 09:54 » 

Действительно, не логично выходит. Тут явная описка.
Да простит меня Alf, я исправил этот текст.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.

Хз, я не очень просто не очень во всё это верю, во всякие там сатурны и прочую поебень.
Alf
Гость
« Ответ #69 : 23-10-2005 13:27 » new

Спасибо обоим. Странно, что никто раньше не заметил.
Записан
Страниц: 1 2 [3]  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines