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

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

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

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

Дополнительно найдем точку O, которая принадлежит многоугольнику H, но не совпадает ни с одной из точек множества M: возьмем для этого какие-нибудь две точки из M и найдемсередину соединяющего их отрезка (если впоследствии вдруг окажется, что эта точка принадлежит M, то можно будет удалить ее из M,так как она заведомо не является вершиной H).Используя какую-нибудь сортировку с помощью сравнений, всеточки множества M можно упорядочить по возрастанию углов междуотрезком OP и отрезками, соединяющими O с точками множества M,при этом мы считаем, что величина каждого угла принадлежит полуинтервалу [0, 2π). Если вдруг обнаружится, что два каких-то угла равны, то упорядочим соответствующие точки по удаленности от O, нодля краткости будем говорить просто о сортировке по величине угла.Соединив точки в этом порядке (будем обозначать их P1 , P2 , ..., Pn , приэтом P1 = P), и соединив дополнительно Pn c P1 , мы получим замкнутую несамопересекающуюся ломаную, но ограниченный этой ломаной многоугольник может не быть выпуклым (см.

рис. а). Тогда среди вершин P2 , P3 , ..., Pn найдется хотя бы одна, скажем Pk , вдавленная,которая принадлежит треугольнику Pk−1 OPk+1 при k < n и треугольнику Pn−1 OP1 при k = n (рис. б). Вдавленную вершину можно исключить из дальнейшего рассмотрения, соединив напрямую Pk−1 с Pk+1 ,или, соответственно, P1 с Pn−1 . Удалив все вдавленные вершины, мыполучим требуемый многоугольник.

Такова общая идея алгоритма.Задержимся на удалении вдавленных вершин.«Наглядно можно представлять себе дело так: в точках M вбиты гвозди, на которые натянута резинка, охватывающая их все, — эта резинка и будет выпуклой оболочкой множества гвоздей» []. Но в нашем понимании построение выпуклой оболочкипредполагает еще перечисление вершин в порядке их обхода.§ . Асимптотические оценки (два примера)P5P8P5P8P6P7P4а)OP1P6P7P3P4б)OP2P3P2P1Рис. . a) Точки, упорядоченные по величине угла ∠ P1 OPi , i = 1, 2, ..., n; б) вершина P4 — первая вдавленная вершина в последовательности P2 , P3 , ..., P8 .Вдавленные вершины можно обнаружить просмотром точекP2 , P3 , ..., Pn , P1 : переходя от вершины Pi к вершине Pi+1 , i = 2, 3, ......, n − 1, можно сразу проверять, принадлежит ли Pi треугольникуPi−1 OPi+1, а при переходе от Pn к P1 проверять, принадлежит ли Pnтреугольнику Pn−1 OP1 .

Если да, то Pi или соответственно Pn , удаляется, но после этого надо проверить, не окажется ли теперь вдавленнойпредыдущая из неудаленных вершин, — на рис. б видно, что послеудаления P4 вершина P3 становится вдавленной. Возможно, что удаление одной вдавленной вершины повлечет удаление нескольких ужерассмотренных вершин, но вершина P1 никогда не будет удалена.При i < n − 1 после Pi+1 мы рассматриваем Pi+2 и вновь пытаемсяосвободиться от вдавленных вершин с меньшими номерами и т.

д.Последний шаг — переход от Pn к P1 и завершающая попытка освободиться от вдавленных вершин.Затраты этапа построения точек P и O ограничены значением c1 n,где c1 — некоторая константа.Если используется сортировка, сложность которой по числу сравнений есть r(n), то в алгоритме Грэхема может потребоваться не более c2 r(n) операций для сортировки точек по величине угла, константа c2 отражает затраты на сравнение двух углов и сравнение расстояний от O до двух данных точек.Покажем, что описанный процесс удаления вдавленных вершинпотребует затрат, не превосходящих по величине c3 n, где c3 — некоторая константа (в частности, учитывающая затраты на проверку принадлежности точки треугольнику). В самом деле, если переход от Piк Pi+1 сопровождается проверкой вдавленности некоторого числа vi Глава .

Сложности алгоритмов как функции числовых аргументоввершин, то число удаленных при этом вершин равно vi − 1. Но обnP(vi − 1) < n, и,щее число удаленных вершин меньше n. Поэтомукак следствие,i =2nXvi < 2n.(.)i =2Это означает, что сложность TG (n) алгоритма Грэхема по общемучислу арифметических операций и сравнений не превосходит c′ r(n) ++ c′′ n, где c′ и c′′ суть некоторые положительные константы. Сложность любой сортировки массивов длины n по числу сравнений неможет быть меньше n/2, так как каждый элемент должен пройти хотя бы одно сравнение и в каждом сравнении участвуют два элемента.Имеемn¶ r(n)(c′ + 2c′′ ),TG (n) ¶ c′ r(n) + c′′ n = r(n) c′ + c′′r(n)откуда TG (n) = O(r(n)).

При этом у нас нет пока достаточных оснований для утверждения, что TG (n) = Θ(r(n)), потому что нет, например,оснований утверждать, что после выбора P и O может действительно потребоваться r(n) сравнений обсуждаемого типа (ведь мы можемеще выполнять арифметические операции; почему бы не предположить, что, прибегая к ним, можно существенно снизить число сравнений при сортировке), и мы пока можем утверждать только то, чтоTG (n) = Ω(n); эту тему мы отложим до § .После того как точки упорядочены по величине угла, информацию об их координатах можно представить в виде двунаправленного списка, и тогда удаление вдавленных вершин не будет связанос какими-либо перемещениями координат точек, и, подходя формально, можно было бы затраты на перемещения в процессе удалениявдавленных вершин считать равными нулю.

При менее формальномподходе эти затраты можно считать ограниченными сверху значением cn, где c — некоторая константа: переход от массива к двунаправленному списку и, равным образом, в силу (.), работа со ссылкамиво время удаления вдавленных вершин потребуют затрат, ограниченных величинами такого вида.

В свою очередь, сложность любой сортировки по числу перемещений элементов не может быть меньшечем n/2 (так как не исключено, например, что изначальный порядок элементов является обратным к требуемому). Отсюда сложностьалгоритма Грэхема по числу перемещений не превосходит произведения некоторой константы и сложности используемой сортировкипо числу перемещений. Аналогично, для сложности по общему чис-§ .

Асимптотические оценки (два примера)лу арифметических операций, сравнений и перемещений мы имеемоценку O(s(n)), где s(n) — соответствующая сложность используемойсортировки.Основываясь на эскизном описании алгоритма Грэхема, мы получили следующее.Для любой сортировки массивов длины n, имеющей некоторуюсложность s(n) по общему числу сравнений и перемещений элементов, существует алгоритм построения выпуклой оболочки n точек,заданных массивом своих координат на плоскости, сложность которого по общему числу арифметических операций, сравнений и перемещений есть O(s(n)).Пространственная сложность алгоритма Грэхема, очевидно, естьO(n).Пример ..

Пусть G = (V , E) — ориентированный граф без кратных ребер и v ∈ V . Вояжем по G, выходящим из вершины v, будемназывать любой путь, который• начинается в вершине v,• не проходит ни по одному из ребер дважды,• завершается в вершине, из которой не выходит ни одного непройденного ребра(вояж не обязательно охватывает все ребра G). Примером выходящего из вершины 1 вояжа в изображенном на рис.  графе служит(1, 2, 2, 3, 1, 4).4351267Рис.

. Ориентированный граф.Построение какого-то одного выходящего из данной вершины vвояжа может быть выполнено произвольным блужданием по непройденным ребрам графа, завершающимся в вершине, из которой невыходит непройденных ребер. Систематизация блужданий может со- Глава .

Сложности алгоритмов как функции числовых аргументовстоять в том, что, попав в некоторую вершину, мы выбираем дляпродолжения пути ребро, ведущее в вершину с наименьшим доступным номером.Определяемый этим алгоритмом вояж может захватить и все ребра — например, когда граф имеет вид кольца (на рис.  изображентакой граф, для которого | E | = | V | = 5).

Входом алгоритма являетсяграф G и вершина v. Если мы рассматриваем | E | как размер входа, то для сложно3сти любого алгоритма построения вояжаобязательно имеет место нижняя оценка Ω(| E |) — ввиду, например, того, что42для любого фиксированного | E | существует граф, имеющий вид кольца. Возникает вопрос, можно ли обосновать верхнююоценку O(| E |)? Если да, то в итоге это дало бы оценку Θ(| E |).51Для представления графов, не имеющих кратных ребер, часто используютсяРис.

. Граф в виде кольцаматрицы смежности. Матрица смежно(любой вояж охватываетсти — квадратная матрица порядка | V |,все ребра).состоящая из нулей и единиц (фактически, булева матрица), в которой элементс индексами i, j равен единице, если и только если из i-й вершинывыходит ребро в j-ю вершину. Такой способ представления действительно удобен во многих задачах. Но когда речь идет о блужданиях по графу, при которых однажды пройденное ребро изымается издальнейшего рассмотрения, более удобным оказывается представление графа в виде массива a1 , a2 , ..., a| V | списков смежных вершин.В списке ai , i = 1, 2, ..., | V |, в порядке возрастания содержатся номеравершин, в которые входят ребра, выходящие из вершины с номером i.Для графа, приведенного на рис. , имеемa1 = (2, 4), a2 = (2, 3), a3 = (1, 4), a4 = (), a5 = (6), a6 = (5), a7 = ();для графа в виде кольца —a1 = (2), a2 = (3), ...,a| V |−1 = (| V |),a| V | = (1)(в этом графе | V | = | E |).

Представление в виде массива списков смежных вершин возможно и для графов, имеющих кратные ребра; в этомслучае номера вершин в каждом списке располагаются в порядкенеубывания.§ . Асимптотические оценки (два примера)Начав вояж из вершины с номером v, мы смотрим, не пуст ли список av : если он пуст, то вояж закончен. Если же список av не пуст, переносим первый его элемент (пусть это будет, например, i) в списоквершин, через которые шаг за шагом проходит вояж; затем рассматриваем список ai , если он пуст, то вояж закончен, иначе повторяемвсе то же самое, что проделывали в предыдущей вершине, и т.

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

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

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