Главная » Просмотр файлов » Лекции о сложности алгоритмов. С. А. Абрамов

Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 12

Файл №1121249 Лекции о сложности алгоритмов. С. А. Абрамов (Лекции о сложности алгоритмов. С. А. Абрамов) 12 страницаЛекции о сложности алгоритмов. С. А. Абрамов (1121249) страница 122019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Рассмотрим сложность в среднем ¯T¯QS (n) быстрой сортировки по числу сравнений. Будем считать, что в качестве разбивающего элемента всегда выбирается первый элемент сортируемой частимассива. Введем случайную величину ξn на Πn , равную числу сравTнений быстрой сортировки для a ∈ Πn (в этом смысле ξn (a) = CQS(a)).ИмеемX¯T¯QS (n) = Eξn = 1ξn (a).n!a∈ΠnВведем разложениеΠn = Kn1 + Kn2 + ... + Knn ,где событию Kni принадлежат все те перестановки длины n, для которых разбивающий элемент занимает i-ю позицию после завершенияразбиения.

В силу предложения .(i) (видно, что Kni = Fni,1 — событиесостоит в том, что -й элемент перестановки равен i), получаем1nPn (Kni ) = ,i = 1, 2, ..., n.Разбиение перестановки a (первый этап быстрой сортировки) порождает две перестановки a′ ∈ Πi−1 и a′′ ∈ Πn−i . В соответствии с этимопределим еще две случайные величиныξ′n (a) = ξi−1(a′ ),ξ′′n (a) = ξn−i (a′′ ),где i — номер позиции, которую занимает разбивающий элемент после разбиения. По формуле полного математического ожиданияEξ n =nXi =1E(ξn | Kni )Pn (Kni ) =nX1(n − 1 + E(ξ′n | Kni ) + E(ξ′′n | Kni )) ;i =1nГлава . Сложность в среднемпосле очевидного упрощения имеемEξ n = n − 1 +1nnXi =1(E(ξ′n | Kni ) + E(ξ′′n | Kni )).Займемся вычислением E(ξ′n | Kni ) и E(ξ′′n | Kni ), 1 ¶ i ¶ n.Мы имеем разложениеXKni =Gni,p ,p ∈Πi−1i,pгде событие Gn определено так же, как в предложении .(ii), — этособытие состоит в том, что относительный порядок элементов перестановки, имеющих значения, меньшие i, совпадает с порядком элементов перестановки p длины i − 1; имеемXE(ξ′n | Kni ) =E(ξ′n |Gni,p )Pn (Gni,p ).p ∈Πi−1i,pКогда выполняется Gn , значение ξ′n (a) равно ξi−1 (p).

Принимая дополнительно во внимание предложение .(ii), имеемX1= E ξ i −1 .E(ξ′n | Kni ) =ξi−1 (p)(i − 1)!p ∈Πi−1Аналогично можно показать, чтоXξn−i (p)E(ξ′′n | Kni ) =p ∈Πn−i1= Eξ n − i ;(n − i)!здесь надо рассмотреть событие, которое состоит в том, что относительный порядок элементов перестановки, имеющих значения, большие i, совпадает с порядком элементов перестановки p длины n − i.В итоге получаемEξ n = n − 1 +Так какnPi =1E ξ i −1 =nPi =1Eξ n − i =1nnP−1nXi =1(Eξi−1 + Eξn−i ).Eξk , тоk =0Eξ n = n − 1 +2nn −1Xk =0Eξ k .(.)§ . Пример медленного роста сложности в среднемТаким образом, для ¯T¯QS (n) = Eξn мы имеем соотношениеn −1X¯T¯QS (k),¯T¯QS (n) = n − 1 + 2n(.)k =0¯T¯QS (0) = 0. Домножение обеих частей равенства (.) на n даетn¯T¯QS (n) = n(n − 1) + 2n −1X¯T¯QS (k).k =0При n > 0 имеем для n − 1:(n − 1)¯T¯QS (n − 1) = (n − 1)(n − 2) + 2n −2X¯T¯QS (k).k =0Вычитая почленно последнее равенство из предпоследнего, получаемn¯T¯QS (n) − (n − 1)¯T̄QS (n − 1) = 2(n − 1) + 2¯T¯QS (n − 1),т.

е.n¯T¯QS (n) − (n + 1)¯T¯QS (n − 1) = 2(n − 1).Делим последнее равенство на n(n + 1) и переходим к новой неизвестной функции t(n) =¯T¯QS (n):n+1t(n) − t(n − 1) = 2n−1,n(n + 1)t(0) = 0.Решением любого уравнения вида t(n) − t(n − 1) = ϕ (n) при функцииnPϕ , определенной для всех n ¾ n0 , является t(n) = ϕ (n0 ) +ϕ (k),k = n 0 +1n ¾ n0 (легко доказывается индукцией по n в предположении, что если нижний предел суммирования больше верхнего, то сумма равнанулю). В нашем случаеt(n) = 2nXk =1Мы имеемnPk =1поскольку рядотсюдаk−1=2k(k + 1)nXk =11−2k+1nXk =11.k(k + 1)(.)nP11= ln n + O(1); с другой стороны,= O(1),k+1k(k+ 1)k =1∞Pk =11сходится. Таким образом, t(n) = 2 ln n + O(1);k(k + 1)¯T¯QS (n) = (n + 1)t(n) = 2n ln n + O(n).(.)Глава .

Сложность в среднемВ то же время, сложность в худшем случае TQS (n) есть величина порядка n2 (см. задачу ).Число перемещений, требуемое быстрой сортировкой для конкретного массива, не превосходит числа сравнений, домноженногона некоторую небольшую константу, откуда сложность в среднем¯T¯′ (n) по числу перемещений элементов допускает оценку ¯T¯′ (n) =QSQS= O(n log n).Сложность в среднем быстрой сортировки как по числу сравнений,так и по числу перемещений элементов допускает оценку O(n log n).Быстрая сортировка не использует дополнительных массивов, поэтому пространственная сложность по числу одновременно хранимыхдополнительных величин, равных каким-то элементам исходного массива, ограничена (небольшой) константой и, как следствие, допускает оценку O(1).Нелишне заметить, что если быстрая сортировка реализована какрекурсивная процедура, то при ее выполнении будет использованстек отложенных заданий.

Рекурсию в данном случае можно организовать так, что в стек будут попадать лишь значения индексов некоторых элементов, но не сами элементы массива. В соответствии с определением алгебраической сложности объем такого стека не влияет напространственную сложность.Если выйти за рамки алгебраической сложности, то размер стекаотложенных заданий становится важной характеристикой алгоритма. Мы рассмотрим размер этого стека для некоторого типа рекурсивных сортировок, к которому относится не только быстрая сортировка, но и, например, рекурсивный вариант сортировки слияниями.Пусть сортировка организована так, что на первом ее этапе мы, следуя некоторому принципу, выделяем из массива x длины n > 1 двекакие-то его непересекающиеся части x ′ , x ′′ , длина каждой из которых меньше n.

На втором этапе эти части сортируются рекурсивнос помощью той же сортировки, и на третьем, заключительном, этапе,исходя из результатов сортировки x ′ и x ′′ , массив x представляется,уже без рекурсий, в упорядоченном виде. Если n = 0 или n = 1, тоникаких действий над элементами массива не производится.Будем использовать для такого рода сортировок рабочее название«бинарные рекурсивные сортировки». Возникающие при выполнениитаких сортировок рекурсии реализуются с помощью стека отложенных заданий.Теорема .. Если некоторая бинарная рекурсивная сортировкатакова, что первым из x ′ , x ′′ сортируется массив, имеющий не пре-§ .

Пример медленного роста сложности в среднемnдлину, то в ходе применения сортировки к массиву xвосходящую2длины n > 1 число отложенных заданий, хранящихся в стеке, никогдане превосходит log2 n.Доказательство. Проведем индукцию по n. При n = 2 утверждение, очевидно, справедливо. Пусть утверждение доказано для2, 3, ..., n − 1, и пусть массив x, содержащий n элементов, на первомэтапе сортировки порождает два массива x ′ , x ′′ , причем длина n′nпервого массива x ′ не превосходит , длина n′′ второго массива x ′′2не превосходит n − 1.

Пусть n′′ ¾ n′ ¾ 1. На протяжении сортировкимассива x ′ , помимо отложенных заданий, связанных с сортировкойx ′ , в стеке будет храниться еще одно задание — сортировать x ′′ .Но в момент, когда сортировка массива x ′ завершена, в стеке неостанется никаких ее следов; таким образом, по предположениюиндукции, число отложенных заданий в стеке никогда не превзойnдет max{log2 n′ + 1, log2 n′′ }.

В силу того, что n′ ¶ и n′′ ¶ n − 1, мы2имеемmax{log2 n′ + 1, log2 n′′ } ¶ log2 n,что и требовалось.Полученная оценка числа отложенных заданий, хранящихся в стеке, является оценкой для сложности в худшем случае и, тем самым,для сложности в среднем тоже.Принимая во внимание теорему ., мы приходим к варианту быстрой сортировки, представляемому рекурсивной процедурой qsort(k, l),обращение к которой обеспечивает сортировку части xk , xk+1 , ..., xl исходного массива x1 , x2 , ..., xn ; при k ¾ l никаких действий не производится. Сам массив x1 , x2 , ..., xn является глобальным по отношениюк процедуре:if k < l thenxk выбирается в качестве разбивающего элемента и выполняется разбиение xk , xk+1 , ..., xl ; пусть i — индекс, получаемый разбивающим элементом после разбиения;if i − k < l − i then qsort(k, i − 1); qsort(i + 1, l) elseqsort(i + 1, l); qsort(k, i − 1)fifi.Быстрая сортировка всего массива является результатом выполненияqsort(1, n).Глава .

Сложность в среднем§ . Функция затрат рандомизированного алгоритмаОпределение .. Алгоритмы с элементами случайности, реализуемыми обращениями к генераторам случайных чисел, называютсярандомизированными.Рандомизированные алгоритмы можно разделить на вероятностные, или, что то же самое, алгоритмы типа Монте-Карло, и алгоритмытипа Лас-Вегас.

Первый тип допускает, что ответ, который дает алгоритм для поставленной задачи с некоторым конкретным входом, можетбыть неправильным, хотя бы и с малой вероятностью; второй тип —Лас-Вегас — гарантирует правильный ответ, но (как и для алгоритмовтипа Монте-Карло) время получения ответа для конкретного входане определяется, вообще говоря, однозначно этим входом  . Исключаяспециально оговариваемые редкие случаи, мы будем рассматриватьтолько алгоритмы типа Лас-Вегас, не упоминая этого каждый раз.Анализ сложности рандомизированного алгоритма сводится к нахождению математических ожиданий некоторых случайных величин.Но ситуация здесь отличается от той, когда множество входов фиксированного размера рассматривается как вероятностное пространство и затраты алгоритма, однозначно определенные для каждогоконкретного входа, становятся случайными величинами на этом пространстве (мы шли этим путем в двух предыдущих параграфах).

Приисследовании рандомизированных алгоритмов вероятностное пространство, на котором рассматриваются случайные величины, состоит из сценариев выполнения алгоритма для фиксированного входа,и каждый сценарий определяется тем, какие случайные числа будут сгенерированы в соответствующие моменты выполнения алгоритма; за каждым таким сценарием закрепляется некоторая вероятность. В нашем контексте генератор случайных чисел можно представлять себе как стандартную функцию random(N) целого положительного аргумента N, результатом выполнения которой является элемент множества {0, 1, ..., N − 1}, но невозможно предсказать точно,каким именно будет значение этой функции, — любой из элементовуказанного множества может появиться с вероятностью 1/ N.Таким образом, затраты рандомизированного алгоритма при фиксированном входе, вообще говоря, не определяются однозначно, ноЭта классификация является достаточно распространенной в специальной литературе по рандомизированным алгоритмам — см., например, книгу [], — но не единственной.

Например, в [, разд. .] рандомизированные алгоритмы подразделяютсяиначе, а именно — на алгоритмы типа Монте-Карло, типа Лас-Вегас и шервудские. Мыне будем останавливаться на этом.§ . Функция затрат рандомизированного алгоритмазависят от сценария вычисления. При фиксированном входе мы можем рассмотреть множество всех сценариев и, приписав адекватнымобразом каждому из сценариев некоторую вероятность, ввести на полученном вероятностном пространстве случайную величину, значение которой для данного сценария равно соответствующим вычислительным затратам. Значение функции затрат на данном входе можноположить равным математическому ожиданию этой случайной величины (усредненным затратам для данного входа).

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

Список файлов лекций

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