Алгоритмы - построение и анализ (1021735), страница 26
Текст из файла (страница 26)
Их метод подходит для решения рекуррентных соотношений вида (4. 15) Т (и) = ~~~ а;Т ([™(Ь~ ) + ~ (и), Глава 4. Рекуррентные соотношения 139 где Й > 1; все коэффициенты а; положительны, и в сумме содержится хотя бы одно слагаемое; все 6; больше 1; функция /(и) ограниченная, положительная и неубывающая. Кроме того, для любой константы с > 1 существуют константы по и Ы > О, такие что для всех и > по справедливо соотношение / (п/с) > цГ' (и).
Этот метод позволяет найти решение рекуррентного соотношения Т (и) = Т (1п/31') + Т ((2п/31') + О (и), для которого неприменим основной метод. Чтобы решить рекуррентное соотношение (4.15), сначала найдем такое значение р, при котором 2 ', а;6, " = 1. (Такое р всегда существует, причем оно всегда единственное и положительное.) Решением рекуррентного соотношения является Т(п) = ст(тР)+ тз пг ~ — Нх ! У(х) ~ хя+1 и' где и' — достаточно большая константа. Метод Акры-Баззи на практике может оказаться слишком сложным в применении, однако он позволяет решать рекуррентные соотношения, моделирующие разбиение задачи на существенно неравные подзадачи. Основной метод более прост в использовании, однако он применим только в случае подзадач одинаковых размеров. ГЛАВА 5 Вероятностный анализ и рандомизированные алгоритмы Эта глава знакомит читателя с вероятностным анализом и рандомизированными алгоритмами.
Тем, кто не знаком с основами теории вероятности, следует обратиться к приложению В, в котором представлен обзор этого материала. В данной книге мы будем несколько раз возвращаться к вероятностному анализу и рандомизнрованным алгоритмам. 5.1 Задача о найме сотрудника Предположим, предприниматель хочет взять на работу нового офис-менеджера. Сначала он попытался найти подходящую кандидатуру самостоятельно, но неудачно, поэтому решил обратиться в агентство по трудоустройству. Согласно договоренности, агентство должно присылать работодателю по одному кандидату в день. Предприниматель проводит с каждым из этих кандидатов собеседование, после чего принимает окончательное решение, брать его на работу илн нет.
За каждого направленного ему кандидата предприниматель платит агентству небольшую сумму. Однако наем выбранного кандидата на работу фактически стоит дороже, поскольку при этом необходимо уволить офис-менеджера, работающего в данное время, а также уплатить агентству более значительную сумму за выбранного кандидата. Предприниматель пытается сделать так, чтобы должность всегда занимал наиболее достойный из всех кандидатов. Как только квалификация очередного претендента окажется выше квалификации офис-менеджера, который работает в данное время, этот офис-менеджер будет уволен, а его место займет более Глава 5. Вероятностный анализ и рандомизированные алгоритмы 141 подходящий кандидат. Работодатель готов понести все необходимые расходы, но хочет оценить, во что обойдется ему подбор нового сотрудника.
В представленной ниже процедуре Нщн Азз1зтлнт эта стратегия найма представлена в виде псевдокода. В ней предполагается, что кандидаты на должность офис-менеджера пронумерованы от ! до п. Предполагается также, что после собеседования с 1-м кандидатом есть возможность определить, является ли он лучшим, чем все предыдущие. В процессе инициализации процедура создает фиктивного кандидата номер О, квалификация которого ниже квалификации всех остальных: Нщв АзязтАнт(гт) 1 Веа1 — О с Кандидат Π— наименее квалифицированный 1> фиктивный кандидат 2 1огт — 11оп 3 бо Собеседование с кандидатом 1 4 11 кандидат 1 лучше кандидата Вез1 5 Феп Веа1 — 1 6 Нанимаем кандидата 1 Модель стоимости этой задачи отличается от модели, описанной в главе 2.
Если ранее в качестве стоимости алгоритма мы рассматривали время его работы, то теперь нас интересует денежная сумма, затрачиваемая на собеседование и наем при использовании данного алгоритма найма работника. На первый взгляд может показаться, что анализ стоимости этого алгоритма очень сильно отличается, например, от анализа времени работы алгоритма сортировки методом слияния. Однако оказывается, что при анализе стоимости и времени выполнения применяются одинаковые аналитические методы. В обоих случаях подсчитывается, сюлько раз выполняется та или иная операция.
Обозначим стоимость собеседования через с;, а стоимость найма — через сы Пусть тп — количество нанятых сотрудников. Тогда полная стоимость, затраченная при работе этого алгоритма, равна 0 (пс, + гпсь). Независимо от того, сюлько сотрудников было нанято, интервью нужно провести с п кандидатами, поэтому суммарная стоимость всех интервью является фиксированной и равна поь Таким образом, нас интересует анализ величины тсь — стоимости найма, которая, как нетрудно понять, меняется при каждом выполнении алгоритма.
Этот сценарий служит моделью распространенной вычислительной парадигмы. Часто встречаются ситуации, когда нужно найти максимальное или минимальное значение последовательности„для чего каждый ее элемент сравнивается с текущим "претендентом" на звание подходящего. Задача о найме моделирует частоту, с которой придется заново присваивать метку "победителя" текущему элементу. Часть !.
Основы 142 Анализ наихудшего случая В наихудшем случае работодателю приходится нанимать каждого кандидата, с которым проведено собеседование. Эта ситуация возникает, когда кандидаты приходят в порядке возрастания их квалификации. При этом процедура найма повторяется п раз, а полная стоимость найма равна О (пса). Однако маловероятно, чтобы кандидаты поступали в указанном порядке. Фактически мы не имеем представления о том, в каком порядке они будут приходить, и никак не можем повлиять на этот порядок. Таким образом, возникает закономерный вопрос, чего следует ожидать в типичном (или среднем) случае. Вероятностный анализ Вероятностный анализ — это анализ задачи, при котором используются вероятности тех или иных событий.
Чаще всего он используется при определении времени работы алгоритма. Иногда такой анализ применяется и для оценки других величин, таких как стоимость найма в процедуре Н!ке Азз!атлет. Для проведения вероятностного анализа необходимо располагать знаниями (или сделать предположение) о распределении входных данных. При этом в ходе анализа алгоритма вычисляется математическое ожидание времени его работы. На эту величину влияет распределение входных величин, поэтому производится усреднение времени работы по всем возможным входным данным.
Делая предположение о распределении входных величин, нужно быть очень осторожным. В неюторых задачах такие предположения вполне оправданны и позволяют воспользоваться вероятностным анализом как методом разработки эффективных алгоритмов и как средством для более глубокого понимания задачи. В других задачах разумное описание распределения входных величин не удается, и в таких случаях вероятностный анализ неприменим. В задаче о найме сотрудника можно предположить, что претенденты приходят на собеседование в случайном порядке.
Что это означает в контексте рассматриваемой задачи? Предполагается, что любых двух кандидатов можно сравнить и решить, кто из них квалифицированнее, т.е. в принципе всех кандидатов можно расположить в определенном порядке. (Определение полностью упорядоченных множеств приведено в приложении Б.) Таким образом, каждому кандидату можно присвоить уникальный порядковый номер от 1 до п. Назовем операцию присвоения порядкового номера 1-му претенденту тапИ (1) и примем соглашение, что более высокий ранг соответствует специалисту с более высокой квалификацией. Упорядоченное множество (гавИ (1), гопй (2),..., гапИ (и)) является перестановюй множества (1, 2,..., и).
Утверждение, что кандидаты приходят на собеседование в случайном порядке, эквивалентно утверждению, что вероятность любого порядка рангов одинакова и равна количеству перестановок чисел от 1 до и, т.е. и!. Другими словами, ранги образуют случайную равловероятлую лере- Глава 5. Вероятностный анализ и рандомизироаанные алгоритмы 143 столовку, т.е. каждая из и! возможных перестановок появляется с одинаювой вероятностью. Вероятностный анализ задачи о найме сотрудника приведен в разделе 5.2. Рандомизированные алгоритмы Чтобы провести вероятностный анализ, нужно иметь некоторые сведения о распределении входных данных. Во многих случаях мы знаем о них очень мало.
Даже если об этом распределении что-то известно, может случиться так, что знания, которыми мы располагаем, нельзя численно смоделировать. Несмотря на это вероятность и случайность часто можно использовать в качестве инструмента при разработке и анализе алгоритмов, путем придания случайного характера части алгоритма. В задаче о найме сотрудника все выглядит так, как будто кандидатов присылают на собеседование в случайном порядке, но на самом деле у нас нет никакой возможности узнать, так ли это на самом деле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
