С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 18
Текст из файла (страница 18)
> xn ). Замена переменной суммирования даетnXTB (n) =⌈log2 k ⌉.(.)k =1Приведенный выше и дополненный в указании к задаче элементарный выводоценки (.) принадлежит М. Оналбекову; в [, разд. .., упр. ] со ссылкой настатью Я. Микусинского ( г.) приведена оценка, фактически совпадающая с (.),но ее вывод опирается на теорию цепных дробей и не столь элементарен и нагляден.Предположение о том, что TE (a1 ) ∼ logφ a1 , насколько известно автору, не доказанои не опровергнуто ( г.).§ .
Завершимость работы алгоритмаДля получения простой асимптотическойоценки TB (n) воспользуемсяpформулой Стирлинга n! ∼ nn e−n 2πn, или, что то же самое,pn! = nn e−n 2πn(1 + o(1)),которая после логарифмирования принимает видlog2 n! = n log2 n − n log2 e +111log2 n + log2 π + + o(1)222(принято во внимание, что log2 (1 + o(1)) = o(1)). Так как 1 < log2 e << 2, тоn log2 n − 2n < log2 n! < n log2 n − n(.)для всех достаточно больших n; в частности, это означает, чтоlog2 n! = n log2 n + O(n).ИмеемnXk =1⌈log2 k ⌉ =nXlog2 k + O(n) = log2 n! + O(n) = n log2 n + O(n).k =1Отсюда получаем оценкуTB (n) = n log2 n + O(n),(.)из которой следует, в частности, что TB (n) ∼ n log2 n.Таким образом, тщательный анализ суммы (.) не приводит к существенно лучшей, чем (.), оценке, но зато дает асимптотику TB (n).В § будет показано, что из того, что сложность по числу сравнений некоторой сортировки не превосходит n log2 n + cn, где c — некоторая константа, следует, что эта сложность есть n log2 n + O(n).
Изэтого будет следовать, что для сложности по числу сравнений сортировки фон Неймана выполнено TvN (n) = n log2 n + O(n); мы обозначаем эту сортировку буквами vN, от фамилии von Neumann.§ . Завершимость работы алгоритмаЕсли выполнение циклического (итерационного) алгоритма не завершается для некоторого входа v, то сложность этого алгоритма неопределена для значения аргумента, равного kv k.
Поэтому анализсложности алгоритма прямо или косвенно включает исследование завершимости.Установление завершимости может быть рассмотрено и как самостоятельная задача. Когда функция L подбирается для выяснениязависимости числа шагов алгоритма от размера входа задачи, то приГлава .
Оценивание числа шагов (итераций) алгоритманаличии выбора более предпочтительной является функция с медленным ростом (имеется в виду рост при увеличении размера входа);даже если при этом усложняется доказательство того, что L обладаетвсеми нужными свойствами, мы зато получаем более точную оценкучисла шагов алгоритма. Но иногда речь может идти только о доказательстве завершимости работы алгоритма — тогда характер ростафункции L отходит на второй план.
То, что выполнение алгоритма Евклида завершается, было доказано в самом начале обсуждения этогоалгоритма без обращения к функциям с логарифмическим ростом.Пример .. Алгоритм, заданный оператором циклаwhile n > 3 doif 2 | n then n := n2 + 1 else n := n + 1 fiod(запись 2 | n означает, что n делится на 2) завершает свою работудля любого натурального n. Для доказательства достаточно рассмотреть функцию n − (−1)n и убедиться в ее убывании при n > 3 в ходевыполнения алгоритма.Пример ..
Если n — данное неотрицательное целое число, тозавершимость выполнения алгоритмаs := 0;for i = 1 to n do s := s + 1i odочевидна — выполнение оператора цикла завершится после n шагов;легко видеть, что при выполнении этого оператора значение L(n, i) == n − i убывает, оставаясь при этом неотрицательным целым.В доказательствах завершимости, основанных на подборе подходящей убывающей целочисленной функции, используется следующеесвойство множества N неотрицательных целых чисел:Не существует бесконечной убывающей последовательности n0 >> n1 > n2 > ...
элементов множества N.Имеются и другие примеры (частично) упорядоченных множествс этим свойством, и соответствующие порядки используются для доказательства завершимости выполнения алгоритмов .Вместо сложных примеров, мы адресуем читателя к задачам , , заимствованным из [, разд. .]. В книге [] кроме двух названных задач содержится интересныйи полезный материал о частично упорядоченных множествах и некоторых специальных типах таких множеств. (Решения задач , не обязательно должны содержатьявные упоминания порядков на множествах, хотя введение некоторых порядков полностью проясняет ситуацию.)§ .
Завершимость работы алгоритмаУстановление завершимости выполнения алгоритма иногда оказывается очень трудной задачей.Пример .. Завершимость для любого натурального n выполнения алгоритмаwhile n > 1 doif 2 | n then n := n2 else n := 3n + 1 fiodне доказана и не опровергнута по сей день, хотя на это направлялисьсерьезные усилия (см.
[]).В случае рандомизированных алгоритмов мы сталкиваемся(см. ниже пример . и первую часть примера .) с возможностьютого, что алгоритм завершается с вероятностью 1, но математическоеожидание времени от начала выполнения до полного завершенияалгоритма бесконечно. Поэтому утверждения о завершимости возможны в двух формах: завершимость с вероятностью 1 и конечностьожидаемого времени выполнения. Вторая форма является, вообщеговоря, более сильной.Пример .. В теории вероятностей подробно рассматриваетсязадача о блуждании частицы по прямой: за один шаг частица передвигается на 1 вправо или на то же расстояние влево, направление же движения на каждом шаге выбирается случайно, вероятно1сти выбора каждого из направлений одинаковы и равны .
Пусть2в начальный момент частица находится в точке 0, и на прямой отмечена некоторая точка m с целой координатой. Доказывается, чтос вероятностью 1 частица через некоторое время попадает в точку m.Попытаемся теперь вычислить математическое ожидание a времени(общего числа шагов), которое потребуется для достижения точки m.Легко убедиться, что уже в случае m = ±1 это среднее бесконечно.Пусть, например, m = 1.
Используем формулу полного математического ожидания: если шаг сделан вправо, то за этот один шаг мыдостигаем цели, если же шаг сделан влево, то придется дождатьсямомента, когда частица вернется в точку 0 и тем самым повторитсяначальная ситуация:a=1·11+ 2a · .221Если бы a было конечным, это бы дало 0 = . Поэтому среднее бес2конечно.Глава . Оценивание числа шагов (итераций) алгоритмаРассмотрим с этой точки зрения задачу .
Итак, путник столкнулся со стеной, простирающейся бесконечно в обе стороны. Имеетсядверь в этой стене, но путник не знает ни расстояния до двери, нинаправления к ней. Если путник использует алгоритм поиска двери,состоящий в бросании перед каждым шагом монеты для определениянаправления (вправо или влево) этого шага, то он с вероятностью 1найдет дверь, но математическое ожидание числа шагов равно бесконечности, коль скоро в начальный момент путник не стоит прямоперед дверью.
Иными словами, если pk (k ¾ 1) есть вероятность того,что после k шагов путник впервые окажется перед дверью, то∞Xk =1pk = 1 и∞Xkpk = ∞.k =1Пример .. Обратимся к системам автоматизированного обучения. При использовании известного педагогического приема — задания вопросов вразбивку — с каждым выбранным системой вопросомможет быть связана следующая цепочка действий: вопрос обучаемому; прием и проверка ответа; сообщение, правилен ли ответ и объявление правильного ответа, если был дан неправильный ответ.
Нетрудно привести примеры учебных тем, когда такой подход выглядит разумно: таблица умножения, исторические даты, иностранные слова(здесь же — неправильные глаголы), значения иероглифов, названиесозвездий (показываются картинки), определение на слух музыкальных интервалов и т. д. Прообразом одного из алгоритмов выбора вопросов служит способ заучивания ответов с помощью колоды карточек, на лицевой стороне каждой из которых написан вопрос, а наобороте — ответ. Из колоды выбирается наугад карточка, и делается попытка ответить на вопрос.
Если это не удается, ответ прочитывается на обороте. Затем карточка возвращается в колоду, и всеповторяется. На примере колоды карточек предлагаемый рандомизированный алгоритм (называемый алгоритмом кратных карт ) можетбыть проинтерпретирован так: выбранная карточка, содержащая вопрос с известным обучаемому ответом, уже не возвращается в колоду; если же обучаемый не смог дать правильный ответ, то, крометого что в колоду возвращается эта карточка, туда добавляется ещеодин ее экземпляр. Сеанс обучения заканчивается, когда в колоде неостается карточек.Пусть вопросы занумерованы числами 1, 2, ..., n. Каждый этапсеанса обучения характеризуется кратностями m1 , m2 , ..., mn вопроСм. [].§ .
Завершимость работы алгоритмасов (не исключается равенство нулю каких-то кратностей); пустьm = m1 + m2 + ... + mn . Если m = 0, то сеанс заканчивается, иначе выбирается очередной вопрос; вероятность того, что будет выбран i-йmвопрос, должна равняться i .mСеанс обучения становится бесконечным, если, например, с некоторого момента обучаемый начинает давать только неправильные ответы. Но можно интересоваться вероятностями и средним временеможидания некоторых событий в течение этого бесконечного сеанса.Пусть в некоторый момент только один вопрос, скажем, вопрос с номером , имеет кратность 1, а все остальные — кратности большие,чем 1. Предположим, что начиная с этого момента обучаемый стабильно дает неправильные ответы на предлагаемые вопросы.
Найдемвероятность того, что рано или поздно обучаемый получит вопросс номером , а также математическое ожидание времени, проходящего до появления этого вопроса (время измеряется количеством заданных вопросов). Пусть m — суммарная кратность, а n — общее числовопросов, m > n ¾ 2. Вероятность получить вопрос с номером после1i вопросов с другими номерами равна , если i = 0, и равнаmm−1mm+i−21m−1·...·=,mm+1m+i−1 m+i(m + i − 1)(m + i)если i ¾ 1. Поэтому вероятность получить рано или поздно вопросс номером равна1+ (m − 1)mТак как∞Xi =11.(m + i − 1)(m + i)(.)111=−,(m + i − 1)(m + i)m+i−1m+iто для частичной суммыsN =NXi =11(m + i − 1)(m + i)имеемsN =и lim s N =n→∞11−,mm+N1, откуда значение выражения (.) (искомая вероятmность) есть1m−1+= 1.mmГлава . Оценивание числа шагов (итераций) алгоритмаМатематическое ожидание времени есть(m − 1)∞Xi =1i.(m + i − 1)(m + i)(.)∞Piрасходится: члены этого ряда поло(m + i − 1)(m + i) 11жительны, и i-й член есть Θ(является величиной порядка ).iiПри этом рядi =1Отсюда математическое ожидание (.) равно бесконечности.Пусть теперь u вопросов (будем считать, что это вопросы с номерами 1, 2, ..., u) имеют кратность 1, а остальные n − u вопросов — кратность большую, чем 1, и пусть u ¾ 2.