AOP_Tom3 (1021738), страница 53

Файл №1021738 AOP_Tom3 (Полезная книжка в трёх томах) 53 страницаAOP_Tom3 (1021738) страница 532017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 53)

46. [НМ20[ Каково значение выражения (1/2к») );~' Г(х)п' *Ох/(2' ' — 1) при условиях, что в — целое положительное число и О с а < в7 47. [НМ21[ Докажите, что ~ 1>,(п/21) е "1~ — ограниченная функция от н. 48. [НМ24'[ Найдите асимптотическое значение величины Ук, определенной в упр. 38, при помощи методов, аналогичных тем, которые в тексте настоящего раддела использовались для анализа величины О, н получите члены до 0(1). 49. [НМ24) Продолжите асимптатическую формулу (47) для 17„до членов порядка 0(п ). 50.

[НМ24) Найдите асимптотическое значение функции где ш — произвольное фиксированное число, большее 1. (Эта функция при целом и», большем 2, потребуется для исследования общего случая обменной поразрядной сортировки, а также для анализа алгоритмов поиска в "памяти луча" в разделе 6.3.) ° 51. [НМ23) Покажите, что для вывода асимптатического разложения г»(п») можно воспользоваться методом исследования асимптотических задач прн помощи гамма-функций вместо формулы суммирования Эйлера (см. (35)). (Это предоставлнет единообразный способ анализа г»(гп) при всех й без таких трюков, как введение в рассмотрение функции 0 ~(х) = (е * — 1)/х.) 52. [НМ35] (Н. Г.

де Брейн,) Каково асимптотическое поведение суммы ( 2п ) где И(1) — количество делителей числа 17 (Таким образам, И(1) = 1, И(2) = 4(3) = 2, 0(4) = 3, И(5) = 2 и т. д. Этот вопрос возникает в связи с анализом алгоритма прохождения дерева из упр. 2.3.1 11.) Найдите значение величины Я /(~„") до членов порндка 0(п '). 53. [ВМ42) Проанализируйте число проверок разрядов и число обменов, выполняемых при обменной поразрядной сортировке, если исходными данными служат двоичные числа с бесконечной точностью в диапазоне (О., 1), каждый разряд которых независимо принимает значение 1 с вероятностью р. (В основном тексте раздела обсуждался лишь случай, когда р = —; применявшиеся методы можно обобщить дэя произвольного р.) Рассмотрите особо !.

случай„когда р = 1/ф = .61803.... 54. (ИМИ) (С. О. Райс (Б. О. Шее).) Покажите, что У„можно записать в виде и т(» 1 1) т 2х!',/а»(» — 1)... (» — и) 2' ' — 1 ' где С вЂ” замкнутая кривая. охватывающая область около точек 2, 3,..., и. В результате замены С произвольно большой окружностью с центром в начале координат получаем сходящийся ряд .Ь 2, ~ 3) (В(и+1, — 1+тбп!)), (Н„! — 1)и и 2 !п2 2 !п2 >! где 6 = 2»/!в 2 н В(и+1, — 1+!Ми) = Г(и+1)Г( — 1+тЬи!)/Г(и+тЬти) = и!/ П" (6 — 1+тЬти).

° 55. (28) Покажяте, как нужно изменить программу (), чтобы в качестве разделяющего элемента выбиралась медиана из трех ключей (28), полагая М > 1. 50. (М43) Проанализируйте поведение в среднем параметрое, от которых зависит время работы программы Ц, егти программа изменена так, что она выбирает медиану из трех элементов, как в упр. 55 (см упр. 29). 5.2.3. Сортировка посредством выбора Вще адно важное семейство методов сортировки основана на идее многократного выбора.

Вероятна, простейшая сортировка посредствам выбора сводится к следующему. 1) Найти наименьший ключ, переслать соответствующую запись в область вывода н заменить ключ значением са (каторое по предположению больше любого реального ключа). б) Повторить шаг (!). На этот раз будет выбран ключ, наименьший из оставшихся, так как ранее наименыпий ключ был заменен значением аа. ш) Повторять шаг (!) до тех пор, пока не будут выбраны Х записей.

Заметим, что этот метод требует наличия всех исходных элементов да начала сортировки, а элементы вывода порождает последовательно, адин за другим. Картина, по существу, противоположна картине, возникающей при использовании метода вставок, в катаром исходные записи поступают последовательна, но вплоть до завершения сортировки об окончательном результате ничего неизвестно.

На шаге (!) требуется выполнить Х вЂ” 1 сравнений каждый раз„когда выбирается очередная запись. Также необходимо выделить в памяти отдельную область для накопления результата. Имеется очевидный способ несколько поправить ситуацию: выбранное значение записать в соответствующую окончательную позицию, а запись, которая ее занимала, перенести на место выбранной. Тш-да эту позицию ие нужно будет рассматривать вновь при последующих выборах и не придется иметь дело с ключом бесконечно балыпай величины. На этой идее основан наш первый алгоритм сортировки посредствам выбора. Рис.

21. Сортировка посредством простого выбора. Алгоритм Я (Сортировке посредством простого выбора). Записи ВО...,Лк перекампоновываются в пределах того же 'фрагмента памяти. После завершения сортировки их ключи будут упорядочены: К~ ( ... ( Кп. Сортировка базируется на описанном выше методе, если не считать того, что более удобно, оказывается, сначала выбирать наибольший элемент, затем — второй па величине и т. д.

(Рис. 21). Я1. [Цикл по 11] Вьшолнить шаги Я2 и ВЗ при 1' = Х, Ф вЂ” 1,..., 2. ЯЗ. [Найти шах(Кг,..., Кз).) Найти наибольший из ключей Кн К. „..., К~, .пусть это будет К;, где 4 выбирается как можно ббльшим. ЯЗ, [Поменять местами с К,.) Взаимно переставить записи В, +э Л,. (Теперь записи Яу,..., Яи занимают сваи окончательные позиции.) 1 В табл. 1 продемонстрирован процесс выполнения этога алгоритма при обработке шестнадцати ключей, выбранных нами для примеров. Элементы, претендующие на то, чтобы быть максимальными во время поиска на шаге Я2., выделены полужирным шрифтом.

Таблица 1 СОРТИРОВКА ПОСРЕДСТВОМ ПРОСТОГО ВЫБОРА 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703[ 503 087 512 061 703 170 897 275 653 426 154 509 612 677 765[908 503 087 512 061 703 170 765 275 653 426 154 509 612 877[897 908 503 087 512 061 703 170 677 275 853 426 154 509 612~765 897 908 503 087 512 061 612 170 677 275 853 426 154 509~703 765 897 908 503 087 512 061 612 170 509 275 6$3 426 154[677 703 765 897 908 061[087 154 170 275 426 503 509 512 612 653 677 703 765 897 908 Соответствующая М11-программа довольно проста. Программа В (Сортировка посредстпвом простого выбора). Как и в предыдущих программах из этой главы, записи, находящиеся в ячейках от 1МРОТ+1 до 1МРБТ+И, сортируются в пределах того же фрагмента памяти па ключу, который занимает полное слово. Значения регистров таковы: гА = текущий максимум, гП = 1' — 1, г12 ив б 7с (индекс при поиске), г13 = 1.

Предполагается, что Х > 2. 61 ЗТАНТ ЕМТ1 М-1 г1-г; ' и 03 2Н ЕМТ2 0,1 .57 — 1 Я2. Найти шэх(Х~ ...~~:), А <- д — 1. 03 ЕМТЗ 1,1 о' — 1 1+ — 1. 03 1.ВА 1МРОТ,З Х вЂ” 1 гА +- К,. 00 8Н СИРА 1ИРСТ,2 А Об ОСЕ *»3 А Переход, если К; > К». 07 ЕИТЗ 0,2 В Иначе — установнтыде1»й, Об 00й 1ИРСТ,З В гА »- К,. 00 0ЕС2 1 А й»-й — 1. 10 12Р 88 А Повторить, если й > О. 11 1.0Х 1ИРСТ+1, 1 М вЂ” 1 ЯЗ. Па»генлть местами с Й .

12 БТХ 1ИРНТ,З АГ-1 Тй <-Л,. 10 БТА 1ИРСТ+1, 1 Аг — 1 Л, »- гА. 14 0ЕС1 1 Аг — 1 10 11Р 28 Аг — 1 М>1>2, э Время работы этой программы зависит ат числа элементов Аг, числа сравнений А и числа правастороннпх максимумов В. Нетрудно видеть, что независимо от значений исходных ключей Следовательно, переменной является только величина В.

Несмотря на всю безыс- кусность простого выбора, не так-то легко выполнить точный анализ величины В. В упр. 3-6 показано, что В = (ш!и О, аге (И+1)Нн — 2йг, шах (Аг~1'4)). (2) Усовершенствовании простога выбора. Существует ли какай-нибудь способ улучшения метода выбора, используемого в алгоритме БТ Возьмем, к примеру, поиск максимума на шаге Я2: возможен ли существенно более быстрый способ нахождения максимума? Ответ на этот вопрос — нет! Лемма М. В любом алгоритме нахождения максимума среди п элементов, осно- ванном на сравнении пар элементов, необходимо вылолннтсч по крайней мере, и — 1 сравнений. Докаэаглельсглво.

Если выполнена менее и — 1 сравнений, то найдутся хотя бы два элемента, для которых не было обнаружено ни одного элемента, превосходящего их по величине. Следовательно, мы так н не узнаем, какой нз этих двух элементов больше, а значит, не сможем определить максимум. 1 В этом случае особенно интересным оказывается максимальное значение. Стандартное отклонение величины В имеет порядок Агэ14 (см. упр, 7). Таким образом, среднее время работы программы Я равно 2.5Жл+ 3(А'+ 1) Нм+ 3.5йг — 11 машинных циклов, т. е. данная программа работает лишь немногим медленнее программы, реализующей метод простых вставок (программа 5.2.1Б). Интересно сравнить алгоритм Б с сортировкой методом пузырька (элгоритм 5.2.2В), поскольку метод пузырька можно рассматривать как алгоритм выбора, в котором за один раз иногда выбирается более одного элемента.

По этой причине при сортировке методом пузырька выполняется меньше сравнений, чем при простом выборе, и она, как может показаться, предпочтительнее. На в действительности программа 5.2.2В работает более чем вдвое медленнее программы Я! Сортировка методом пузырька проигрывает йз-за того, что выполняется гли»иком много обменов, в то время как при сортировке посредством простого выбора пересылается очень мало данных. Таким образом, процесс выбора, в котором выполняется поиск наибольшего элемента, должен включать не менее и — 1 сравнений.

Характеристики

Тип файла
DJVU-файл
Размер
10,16 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6710
Авторов
на СтудИзбе
287
Средний доход
с одного платного файла
Обучение Подробнее