Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Фибоначчи (1.. Руйопасс(). А. деМуавр (А. 13е МО1иге) впервые использовал метод производящих функций (см. задачу 4.4) для решения рекуррентных соотношений. Основной метод был принят на вооружение после появления работы Бентли (Вепс!еу)ь Хакена (На1сеп) и Сакса (Бахе) [43], в которой было предложено расширение метода, обоснованное в упр. 4.6.2. Кнут (Кппбу) [208]' и Лью (Ьш) [236] показали, каким образом можно решать линейные рекуррентные соотношения с использованием производящих функций. Подробное обсуждение методов решения рекуррентных соотношений можно найти в книгах Пурдома (Рпп1ош) и Брауна (Вгоьип) [285], а также Грехема (Ога)уаш), Кнута и Паташннка (Расаа)упйс) [151]2.

Некоторые исследователи, в число которых входят Акра (А)сга) и Баззи (Вахх1) [13], Роура (Конга) [297], Верма (Чепца) [344] и Яп (Уар) [358], предложили методы решения для более общих рекуррентных соотношений для алгоритмов "разделяй и властвуй", чем решаемые основным методом. Ниже представлены результаты Акра и Ваэзи, усовершенствованные Лейтоном (Ье(ййоп) [227]. Их метод подходит для решения рекуррентных соотношений вида е з( ), если 1 < х < хо, Т(х) = (4.30) , а,Т(Ь,х) + )'(х), если х > хо, где х > 1 является действительным числом, хо представляет собой константу, такую, что хо > 1/Ь, и хо > 1/(1 — Ь,) для 1=1,2,...,1с, а, — положительная константа; с = 1, 2,..., )с, Ь; — константа из диапазона 0 < Ь, < 1; 1 = 1, 2,..., /с, lс > 1 — целочисленная константа, У(х) представляет собой неотрицательную функцию, удовлепюряющую условию лолинамиального роста: существуют положительные константы с1 и сз, такие, что для всех х > 1 при 1 = 1, 2,...,гс и для всех и, таких, что ь;х < и < х, мы имеем с17"(х) < Г(и) < сз Г(х).

(если [г"'(х)! ограничена сверху некоторым полнномом от х, то ф) удовлетворяет условию полиномиального роста. Например, Г"(х) = х 18 х удовлетворяет этому условию при любых действительных константах О и )3.) Имеетсе русский перевод: Д. Кнут. Искусство нрограимировантг, т 1.

Основные авгорнтмы. 3-в юд.— Мг И.Д. "Виньемсз 2000. еИмеешк русский перевод: Р. Грекам, Д. Кнут, О. Пегешиик. Конкретное математика. Математннескнв основы информатика, 2-е нва — Мг И.Д. "Виньимст 2010. ГЛава К Разделяй и властвуй Хотя основной метод неприменим к такому рекуррентиому соотношению, как Т(п) = Т((п/3)) + Т((2п/3)) + 0(п), метод Акра-Баззи в состоянии его решить. Для решения рекуррентного соотношения (4.30) сначала находим такое единственное действительное число р, что 2 '; а;аз = 1. (Такое р всегда имеется.) Тогда решение рекуррентного соотношения имеет вид Т(п) = 9 х" 1+ — Ыи Метод Акра-Баззи несюлью сложен в использовании, но успешно служит для решения рекуррентных соотношений, моделирующих разделение задали на подзадачи существенно разного размера. Основной метод проще в использовании, но применим толью тогда, когда размеры подзадач одинаювы. Глава 5.

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

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

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

Работодатель готов понести все необходимые расходы, но хочет оценить, во что обойдется ему подбор нового сотрудника. В представленной ниже процедуре Нщн-Азщзтлмт эта стратегия найма представлена в виде псевдокода. В ней предполагается, что кандидаты на должность офис-менеджера пронумерованы от 1 до п. Предполагается также, что после собеседования с г-м кандидатом есть возможность определить, является ли он лучшим, чем все предыдущие. В процессе инициализации процедура создает фиктивного кандидата номер О, квалификация которого ниже квалификации всех остальных. Глава 5. Веронтноетный анализ и рандонизированные алеоритты Н!не-АВЯВтАХТ(п) 1 Ьев! = О // Кандидат 0 — фиктивный 2 Гвг з = 1 Гв и // неквалифицированный кандидат 3 Беседа с кандидатом з' 4 зТ кандидат з лучше кандидата Ьев! 5 Ьев! = з 6 Нанять кандидата з Модель стоимости этой задачи отличается от модели, описанной в главе 2.

Если ранее в качестве стоимости алгоритма Н[кп-Азз!Втлмт мы рассматривали бы время его работы, то теперь нас интересует денежная сумма, затрачиваемая на собеседование и наем при использовании данного алгоритма найма работника. На первый взгляд может показаться, что анализ стоимости этого алгоритма очень сильно отличается, например, от анализа времени работы алгоритма сортировки слиянием.

Однако оказывается, что в ходе анализа стоимости и времени выполнения применяются одинаковые аналитические методы. В обоих случаях подсчитывается, сколько раз выполняется та или иная операция. Обозначим невысокую стоимость собеседования как с„а существенно более высокую стоимость найма — как сь. Пусть ти — количество нанятых сотрудников. Тогда полная стоимость, затраченная при работе этого алгоритма, равна 0(с,п + сьзп). Независимо от того, сколько сотрудников было нанято, интервью нужно провести с п кандидатами, поэтому суммарная стоимость всех интервью является фиксированной и равна с,п. Таким образом, нас интересует анализ величины стоимости найма сьт, которая, как нетрудно понять, меняется при каждом выполнении алгоритма.

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

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

Таким образом, возникает закономерный вопрос, чего следует ожидать в типичном (или среднем) случае. Часть 1 Основы 142 Вероятностный анализ Вероятностный анализ — зто анализ задачи, при котором используются вероятности тех или иных событий. Чаще всего он используется при определении времени работы алгоритма. Иногда такой анализ применяется и для оценки других величин, таких как стоимость найма в процедуре Нжп-Аззытлнт.

Для проведения вероятностного анализа необходимо располагать знаниями (или сделать предположение) о распределении входных данных. При этом в ходе анализа алгоритма вычисляется время его работы в среднем случае путем усреднения времени работы по всем возможным входным данным. Вычисленное таким образом время работы называется временем работы в среднем случае. Делая предположение о распределении входных данных, нужно быть очень осторожным.

В одних задачах такие предположения вполне оправданы и позволяют воспользоваться вероятностным анализом как методом разработки эффективных алгоритмов и как средством более глубокого понимания задачи. В других задачах разумно описать распределение входных величин не удается, и в таких случаях вероятностный анализ неприменим. В задаче о найме сотрудника можно предположить, что претенденты приходят на собеседование в случайном порядке. Что это означает в контексте рассматриваемой задачи? Предполагается, что можно сравнить любых двух кандидатов и решить, кто из них квалифицированнее, т.е. в принципе всех кандидатов можно расположить в определенном порядке. (Определение полностью упорядоченных множеств приведено в приложении Б.) Таким образом, каждому кандидату можно присвоить уникальный ранг, используя числа от 1 до п.

Обозначим ранг 1-го претендента как гапкЯ и примем соглашение, что более высокий ранг соответствует специалисту более высокой квалификации. Упорядоченное множество (гапк(1), гоп/с(2),..., гоп/с(п)) является перестановкой множества (1, 2,..., п). Утверждение, что кандидаты приходят на собеседование в случайном порядке, эквивалентно утверждению, что вероятность любого порядка рангов одинакова и равна количеству перестановок чисел от 1 до п, т.е. и!.

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

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