Как найти пересечение событий если известно объединение
Перейти к содержимому

Как найти пересечение событий если известно объединение

  • автор:

Как найти пересечение событий если известно объединение

Логическое пересечение событий обозначается символом AB и означает, что события A и B происходят одновременно.

Запись используется для обозначения объединения событий и означает, что имеет место или событие A, или B, или A и B одновременно.

На рисунке схематически показаны множества событий A и B.

Заштрихованная область является пересечением AB.

Область, ограниченная внешним контуром, является объединением .

.

Теория вероятностей: как научиться предсказывать случайные события

Разбираем основные понятия, решаем задачи и делаем первый шаг на пути к карьере в data science.

Кадр: фильм «Сумерки. Сага. Затмение» / West Video

Дмитрий Зверев

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Продолжаем разбираться с математическими концепциями, на которых держится современное IT. Сегодня поговорим о теории вероятностей — разделе математики, который широко используется в машинном обучении, геймдеве, статистике и науке о данных.

Из этой статьи вы узнаете:

  • Что такое теория вероятностей
  • Какие понятия в неё входят
  • Что такое алгебра событий
  • По каким формулам она работает
  • Как решать задачи по теории вероятностей

Что такое теория вероятностей

Теория вероятностей — это наука, которая изучает мир случайностей и пытается их предсказать. Здесь встречаются такие понятия, как «события» и «вероятности», у которых, в свою очередь, есть свои свойства и операции — о них мы поговорим чуть позже.

Проще всего продемонстрировать, как работает теория вероятностей, на примере подбрасывания монетки. В этом случае у нас есть два варианта: орёл или решка, а значит, шанс выпадения каждой из сторон одинаковый и составляет 50%.

Но как убедиться, что это действительно так? Например, я могу подбросить монетку десять раз, и мне магическим образом девять раз подряд выпадет орёл и один раз решка. Значит ли это, что шанс выпадения орла — 90%? Конечно, нет — и у этого есть научное объяснение.

Дело в том, что теория вероятностей рассматривает случайные события в рамках бесконечности. Иными словами, если мы будем подбрасывать монетку бесконечное количество раз, то шансы выпадения орла или решки будут приближаться к 50%.

В математике такая закономерность называется законом больших чисел, и этот закон — один из фундаментальных для data science. Фишка в том, что чем больше данных мы имеем на руках, тем точнее можно делать предсказания. Подробнее об этом читайте в статье «Математика для джунов».

Такая же логика работает и для других случайных явлений — например, шанс выпадания числа 5 на игральном кубике равен 1 к 6, а вероятность того, что молния ударит в одно и то же место дважды — примерно 1 к 500.

Теория вероятностей помогает нам предсказывать шанс возникновения различных событий, когда ответ не такой однозначный и на события влияет множество факторов.

Основные понятия

Мы упомянули слова «событие» и «вероятность», но не рассказали, что они вообще значат в контексте теории вероятностей. Давайте разбираться.

События

Событие — это всё, что может произойти, когда мы совершаем какое-то действие. Например, если мы бросаем монетку, то событие — это выпадение орла или решки. Чтобы обозначать события, используют заглавные буквы латинского алфавита. Например, для орла можем выбрать букву A, а для решки — B.

Существует много разных видов и классификаций событий, но в этой статье мы остановимся на основных четырёх:

  • Достоверные — те, которые точно произойдут. Если бросить стакан на пол, то с вероятностью 100% он полетит вниз.
  • Невозможные — те, которые никогда не произойдут. Если бросить тот же стакан на пол, то он никогда не полетит вверх (мораль: не стоит бросать стаканы на пол, если, конечно, вы не на МКС).
  • Случайные — те, которые могут произойти, а могут и не произойти. Например, если мы бросаем игральный кубик, то не можем с уверенностью сказать, что выпадет число 2.
  • Несовместимые — те, которые исключают друг-друга. Например, при подбрасывании монетки может выпасть либо орёл, либо решка — оба одновременно они выпасть не могут.

Если собрать все несовместимые события вместе, они будут называться полной группой событий. Это множество событий, одно из которых обязательно случится, если мы совершаем действие, а другие — не произойдут никогда. Например, когда мы бросаем игральный кубик, может выпасть только одна из сторон.

Вероятности

Вероятность — это число, которое обозначает шанс возникновения события. Например, вероятность выигрыша в лотерею может составлять 1 к 1 000 000.

Мы записывали значения вероятностей в процентах и отношениях, но математикам удобнее располагать их в диапазоне от 0 до 1. Если вероятность равна 0, то событие никогда не произойдёт, а если 1 — точно произойдёт. Всё, что посередине, — это случайные события.

Самый простой способ вычислить вероятность — поделить число благоприятных событий на общее число возможных событий. Например, если всего в колоде 36 карт, а мы хотим достать короля пик, то вероятность этого события равна 1/36, или 0,03. Если бы нас устроил любой из королей, то вероятность была бы равна 4/36 — то есть 0,1.

К формулам мы ещё вернёмся, а пока отметим, что вероятность — это не всегда точное предсказание, а лишь оценка шанса возникновения события. Как следует из закона больших чисел, если шанс выпадения орла и решки равен 50%, это не означает, что они будут выпадать по очереди.

Ещё вероятность может быть условной — или зависеть от другого события. Например, если мы хотим вытащить любой туз из колоды карт, шанс равен 4/36. Но если до этого кто-то уже вытащил одного туза, то вероятность будет равна 3/35. Это потому, что в колоде стало на одну карту меньше и количество благоприятных событий тоже уменьшилось.

С определениями закончили — теперь давайте узнаем, как событиями можно управлять.

Что такое алгебра событий

Когда мы считаем вероятности, нас может устраивать более чем один результат событий. Или другая ситуация — нам может быть важно, чтобы два события выполнялись вместе. В таких случаях на помощь приходит алгебра событий. Разбираемся, какие действия она позволяет совершать.

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

Сложение (объединение) событий

Сумма двух событий A + B — это сложное событие, которое произойдёт, если случится или событие A, или событие B, или оба одновременно.

Допустим, мы хотим вычислить вероятность выпадения на кубике стороны с числами 2 или 4. Обозначим событие «выпадение стороны 2» как A, а событие «выпадение стороны 4» как B. Так как у кубика всего шесть граней, вероятность выпадения каждой из этих сторон равна 1/6.

А так как нас интересует либо событие A, либо событие B, мы ищем сумму этих событий — A + B. Вычисляем соответствующие вероятности:

Получается, что шанс выпадения стороны 2 или 4 при броске кубика равен 2 к 6, или 1 к 3, или 33%.

Правило сложения можно применять не только к двум событиям, но и к любому их количеству. Например, событие A + B + C + D произойдёт, если случится хотя бы одно из событий A, B, C, D или одна из их комбинаций, такая как A и C или A, C и D.

Умножение (пересечение) событий

Произведение событий A и B — это событие A × B, которое произойдёт, если случится и событие A, и событие B.

Допустим, мы бросаем монетку два раза и хотим понять, каков шанс, что оба раза выпадет решка. Напомним, что вероятность выпадения решки — 1/2.

Обозначаем события: A — решка выпадает первый раз, B — решка выпадает второй раз. Считаем вероятности:

Получаем, что шанс выпадения решки два раза подряд — 25%.

Как в случае с суммой, произведение событий можно считать для любого количества разных событий. Давайте продолжим пример с монеткой — теперь мы хотим, чтобы она выпала четыре раза подряд.

Добавляем два новых обозначения: C — решка выпадает третий раз, D — решка выпадает четвёртый раз. Вероятности всё те же, считаем их произведение:

Ответ — шанс выпадения решки четыре раза подряд равен 1 к 16, или 6,25%.

Сложение совместимых событий

Когда мы говорили о сложении вероятностей, мы использовали несовместимые события, поскольку при броске кубика может выпасть только одна сторона (или ребро, если вам сильно повезёт).

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

P (A + B) = P (A) + P (B) — P (A ⋅ B)

Примером такого сложения может быть выбор случайных чисел. Допустим, у нас есть набор чисел от 1 до 10 и мы хотим найти вероятность того, что выбранное число будет или нечётным, или делиться на 7 без остатка.

  • Событие A — число нечётное. Вероятность выбрать именно его — 5/10.
  • Событие B — число делится на 7 без остатка. Вероятность — 1/10.

Так как число 7 удовлетворяет обоим условиям, мы имеем дело с совместимыми событиями — то есть они могут происходить одновременно. Подключаем формулу: сначала находим сумму вероятностей, а потом вычитаем из неё вероятность пересечения. Внимание на экран:

Вуаля! Получается, что шанс выполнения одного из двух событий равен 11/20, или 55%.

На этом с алгеброй событий закончим и перейдём к более классическим формулам. Но не пугайтесь, мы всё подробно объясним.

Ещё несколько формул теории вероятностей

Для начала — универсальная формула. Выглядит она так:

Разберёмся, что значат все эти буквы:

  • Функция P вычисляет вероятность того, что произойдёт событие, которое нас устраивает (A);
  • m обозначает общее число возможных событий;
  • n — число благоприятных исходов.

Например, попробуем вычислить по этой формуле вероятность выпадения решки:

Всё в порядке, формула работает.

Давайте усложним задачу: посчитаем вероятность того, что решка выпадет три раза. Для этого нужно разбить событие на несколько уникальных — например, выпадение решки при первом, втором и третьем бросках. Обозначим эти события как B, C и D.

Так как эти события зависимы друг от друга, нам нужно их перемножить — для этого подставляем в нашу формулу числа:

Всё верно — вероятность посчитали правильно.

Из этой формулы можно сделать несколько выводов:

  • Если вероятность равна единице — значит, она достоверная. Смысл в том, что из общего числа событий нам подходят все — то есть событие точно произойдёт.
  • Если вероятность равна нулю — значит, она невозможная. Всё из-за того, что нам не подходит ни одно из имеющихся событий.
  • Если вероятность находится в диапазоне от нуля до единицы — она случайная. Это значит, что общее число результатов больше нуля, но не все из них нам подходят.

Теперь вы знаете достаточно, чтобы решать простые задачи по теории вероятностей, чем мы и займёмся в следующем разделе.

Решаем задачи по теории вероятностей

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

Задача 1. В колоде 52 карты. Мы решили вытащить из неё одну — найдите вероятность того, что это будет туз.

  • Число всех возможных событий — 52, так как в колоде 52 карты.
  • Число благоприятных событий — четыре, так как всего в колоде четыре туза.

Вычислим вероятность того, что из всех карт нам попадётся именно туз:

Теперь посчитаем сумму благоприятных событий:

Ответ: 4/52, или 1/13.

Задача 2. В кармане лежит шесть монет: две рублёвых, две пятирублёвых и две десятирублёвых. Мы по очереди достаём две из них случайным образом. Найдите вероятность того, что они обе будут одного номинала.

Сначала мы достаём первую монету. Это может быть или рубль, или пять, или десять. Получается, вероятность достать монету любого номинала — 1/3.

Теперь достаём вторую монету — она должна быть того же номинала, что и первая. Так как только одна из них удовлетворяет нашим критериям, вероятность этого составляет 1/5. А так как наши события связаны друг с другом, перемножаем вероятности обоих:

Ответ: 1/15.

Задача 3. Вы бросаете игральные кости с шестью сторонами. Найдите вероятность того, что сумма выпавших очков будет равна 7.

Всего существует шесть различных комбинаций, которые дают сумму 7:

Общее число возможных результатов при бросании двух костей равно 6 × 6 = 36. Подставляем наши значения в формулу:

Ответ: 6/36, или 1/6.

Что дальше

В этой статье мы разобрались с базовыми понятиями теории вероятностей. Если хотите лучше разбираться в вопросе, хорошие лекции можно найти здесь и здесь. А на этом бесплатном курсе теория даётся сразу с примерами и упражнениями — полезно, если хотите отточить знания на практике.

Для общего развития можно почитать нашу статью «Математика для джунов» и статью о том, как устроена случайность в играх. А если вы всерьёз нацелены вкатиться в data science и хотите подтянуть математический бэкграунд, для вас есть курс «Основы математики для Data Science».

Читайте также:

  • Интегралы: всё, что вы хотели знать, без интриг и сложных терминов
  • Заняться фронтенд-разработкой в 12 лет, выиграть IT‑чемпионат в 13: история Али Сулейманова
  • Чем различается фронтенд- и бэкенд-разработка

Букву P используют потому, что на английский язык слово «вероятность» переводится как probability.

Учебник по теории вероятностей

Случайное событие определено как событие, которое при осуществлении совокупности условий эксперимента может произойти или не произойти. Если при вычислении вероятности события никаких других ограничений, кроме условий эксперимента, не налагается, то такую вероятность называют безусловной; если же налагаются и другие дополнительные условия, то вероятность события называют условной. Например, часто вычисляют вероятность события $B$ при дополнительном условии, что произошло событие $А$.

Условной вероятностью $P_A(B)=P(B|A)$ (два обозначения) называют вероятность события $В$, вычисленную в предположении, что событие $А$ уже наступило.

Вероятность совместного появления двух зависимых событий равна произведению вероятности одного из них на условную вероятность второго, вычисленную при условии, что первое событие произошло, т.е.

$$P(AB)=P(B)\cdot P(A|B) = P(A) \cdot P(B|A).$$

В частности, отсюда получаем формулы для условной вероятности:

Примеры решений на условную вероятность

Пример. В урне находятся 3 белых шара и 2 черных. Из урны вынимается один шар, а затем второй. Событие В – появление белого шара при первом вынимании. Событие А – появление белого шара при втором вынимании.

Решение. Очевидно, что вероятность события А, если событие В произошло, будет
.
Вероятность события А при условии, что событие В не произошло, будет
.

Пример. В урне 3 белых и 3 черных шара. Из урны дважды вынимают по одному шару, не возвращая их обратно. Найти вероятность появления белого шара при втором испытании (событие В), если при первом испытании был извлечен черный шар (событие А).

Решение. После первого испытания в урне осталось 5 шаров, из них 3 белых. Искомая условная вероятность .

Этот же результат можно получить по формуле
.

Действительно, вероятность появления белого шара при первом испытании
.

Найдем вероятность того, что в первом испытании появится черный шар, а во втором — белый. Общее число исходов — совместного появления двух шаров, безразлично какого цвета, равно числу размещений . Из этого числа исходов событию благоприятствуют исходов. Следовательно, .

Искомая условная вероятность

Пример. В трамвайном парке имеются 15 трамваев маршрута №1 и 10 трамваев маршрута №2. Какова вероятность того, что вторым по счету на линию выйдет трамвай маршрута №1?

Решение. Пусть А — событие, состоящее в том, что на линию вышел трамвай маршрута №1, В — маршрута №2.

Рассмотрим все события, которые могут при этом быть (в условиях нашей задачи): . Из них нас будут интересовать только первое и третье, когда вторым выйдет трамвай маршрута №1.

Так как все эти события совместны, то:

отсюда искомая вероятность

Пример. Какова вероятность того, что 2 карты, вынутые из колоды в 36 карт, окажутся одной масти?

Решение. Сначала подсчитаем вероятность того, что две карты окажутся одной определенной масти (например «пики»). Пусть А — появление первой карты такой масти, В — появление второй карты той же масти. Событие В зависит от события А, т.к. его вероятность меняется от того, произошло или нет событие А. Поэтому придется воспользоваться теоремой умножения в ее общей форме:

,
где (после вынимания первой карты осталось 35 карт, из них той же масти, что и первая — 8).

События, состоящие в том, что будут вынуты две карты масти «пики», масти «треф» и т.д., несовместны друг с другом. Следовательно, для нахождения вероятности их объединения воспользуемся теоремой сложения:
.

Пересечение множества отрезков

Пусть дано множество из [math]n[/math] отрезков и требуется найти все точки их пересечения. Очевидно, что задачу можно решить полным перебором за [math]O(n^2)[/math] ; ясно также, что любой алгоритм будет в худшем случае работать за [math]\Theta(n^2)[/math] (нетрудно привести пример, когда количество пересечений квадратично, а алгоритм обязан сообщить о каждом пересечении). Однако существуют алгоритмы, которые оптимальнее, если количество точек пересечения отрезков невелико. Так алгоритм Бентли-Оттмана (англ. Bentley-Ottmann) позволяет решить задачу о пересечении отрезков, используя [math]O((n+I)\log)[/math] времени и [math]O(n)[/math] памяти, где [math]I[/math] — количество пересечений.

Формальная постановка задачи

Дано: [math]S[/math] — множество замкнутых отрезков на плоскости. Найти все точки их взаимного пересечения, охарактеризовав каждую точку пересечения множеством отрезков, которые участвуют в этом пересечении.

Описание алгоритма

Заметающая прямая и события

Воспользуемся методом заметающей прямой (sweep line), расположенной горизонтально и двигающейся вниз (в сторону уменьшения y-координаты). Нас будут интересовать события (events, event points) трёх типов:

  • верхний конец отрезка,
  • нижний конец отрезка,
  • точка пересечения пары отрезков;

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

Приоритет событий

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

Нам потребуется две структуры данных.

Во-первых, мы будем хранить очередь событий [math]Q[/math] в виде сбалансированного бинарного дерева поиска, что позволит извлекать следующее событие и вставлять новое событие в очередь за [math]O(\log)[/math] , где [math]m[/math] — количество элементов в очереди. Дерево будет отсортировано согласно порядку, введённому выше. Причём вместе с каждым событием мы будем хранить список отрезков, верхней точкой которых он является.

Во вторых, будем хранить статус [math]T[/math] заметающей прямой: множество отрезков, пересекающих заметающую прямую в данный момент времени, упорядоченных слева направо. От статуса нам потребуется оптимальные вставка и удаление отрезков, поэтому по-прежнему удобно воспользоваться бинарным деревом поиска.

Статус заметающей прямой

Соседние отрезки в статусе

Главная идея заключается в том, что мы будем проверять, пересекаются ли два отрезка, если они являются соседними в статусе. Это означает, что каждый отрезок мы будем проверять на пересечение с его левым и правым соседями в статусе. Далее, по ходу выполнения алгоритма, у отрезка могут измениться соседи; когда это происходит мы снова проверяем, не пересекает ли отрезок его новых соседей в статусе?

Далее приведен псевдокод алгоритма, а ниже подробно расписана обработка события определенного типа.

findIntersections(S) Инициализировать Q и T for s in S вставить концы s в Q (вместе с верхним концом вставить сам s) while not Q.empty() p = Q.pop() handleEventPoint(p)

Рассмотрим обработку событий.

  • Верхний конец отрезка. В этом случае мы вставим отрезок в статус и проверим, не пересекает ли он соседние отрезки в статусе. Нас будут интересовать только пересечения ниже заметающей прямой. Естественно, если пересечения будут обнаружены, то они должны быть вставлены в [math]Q[/math] .
  • Пересечение отрезков. Если событие — это точка пересечения двух отрезков, то эти отрезки меняют порядок и у каждого появляется, возможно, новый сосед. Мы проверим каждую пару новых соседей в статусе на пересечение. По-прежнему нас интересуют только пересечения ниже заметающей прямой. Отметим отдельно, что в этом случае найденные пересечения могли уже быть обнаружены ранее (когда пересекающиеся отрезки были соседними в статусе).
  • Нижний конец отрезка. В этом случае мы удалим отрезок из статуса и проверим пару отрезков ставших соседними на пересечение. Как и в предыдущем случае, обнаруженные пересечения могут уже находиться в очереди.

Обработка верхних концов и пересечений

Обработка нижних концов

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

handleEventPoint(p) U(p) = множество отрезков, верхний конец которых есть p // Напомним, что мы храним такие отрезки в Q вместе c p // Далее найдём в T все отрезки, которые содержат p (они будут соседними в дереве) L(p) = множество отрезков, нижний конец которых есть p C(p) = множество отрезков, содержащих внутри себя p if [math] \vert L(p) \cup C(p) \cup U(p) \vert \gt 1[/math] report(p, [math]L(p) \cup C(p) \cup U(p)[/math]) // сообщить о p как о точки пересечения отрезков [math]L(p) \cup C(p) \cup U(p)[/math] T.remove([math]L(p) \cup C(p)[/math]) T.insert([math]C(p) \cup U(p)[/math]) // отрезки должны быть вставлены в порядке, // в котором они пересекают горизонтальную линию, // лежащую немного ниже заметающей прямой // (при удалении-вставке отрезков из C(p) - те поменяют порядок на обратный if [math]C(p) \cup U(p) = \emptyset[/math] s_l = левый сосед p в T s_r = правый сосед p в T findIntersection(s_l, s_r, p) else s1 = самый левый отрезок из [math]C(p) \cup U(p)[/math] в T s_l = левый сосед s1 в T findIntersection(s_l, s1, p) s2 = самый правый отрезок из [math]C(p) \cup U(p)[/math] в T s_r = правый сосед s2 в T findIntersection(s2, s_r, p)
findIntersection(s_l, s_r, p) if not intersects(s_l, s_r) return x = точка пересечения s_l и s_r if x лежит ниже заметающей прямой или на ней справа от p Q.insert(x) // должно работать корректно, если x уже есть в Q

Поддержание статуса при обработке события

Доказательство корректности

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

Пусть [math]p[/math] — точка пересечения нескольких отрезков, причем [math]p[/math] не совпадает ни с одним из концов отрезков, участвующих в пересечении. Отсортируем отезки по углу вокруг [math]p[/math] и пусть отрезки [math]s_i[/math] и [math]s_j[/math] окажутся соседними в сортировке. Тогда существует событие [math]q[/math] с приоритетом выше, чем у [math]p[/math] , такое что при обработке этого события [math]s_i[/math] и [math]s_j[/math] будут соседними в статусе.

Алгоритм сообщает о всех точках пересечения

Воспользуемся индукцией по событиям, отсортированным в порядке, введённом выше ( [math]p \lt q \Leftrightarrow p_y \lt q_y \lor p_y = q_y \land p_x \lt q_x[/math] ). Пусть [math]p[/math] — точка пересечения. Предположим что все события [math]q, q \lt p[/math] были обработаны корректно. Тогда [math]p[/math] будет обнаружена.

Действительно, если [math]p[/math] — конец некоторого отрезка, то [math]p[/math] добавлена в очередь событий в начале работы. Все содержащие её отрезки из статуса, который будет текущим при обработке [math]p[/math] будут найдены. Для остальных отрезков, содержащих [math]p[/math] , верно, что [math]p[/math] — их верхний конец, и они будут найдены, т.к. мы храним их вместе с [math]p[/math] в очереди.

Оценка времени работы

Время работы алгоритма — [math]O((n+I)\log)[/math] , где [math]I[/math] — количество пересечений.

Инициализация [math]Q[/math] может быть выполнена за [math]O(n\log)[/math] , инициализация [math]T[/math] — за [math]O(1)[/math] .

Далее, по ходу алгоритма мы обрабатываем каждое событие. Обработка включает в себя удаление события ( [math]O(\log)[/math] ), вызов функции findIntersection до двух раз, что может вызвать вставку новых событий [math]O(\log)[/math] . Также при обработке события [math]p[/math] мы [math]m(p) = \vert L(p) \cup C(p) \cup U(p) \vert[/math] раз выполняем операции вставки, удаления, поиска над [math]T[/math] . Каждая из этих операций требует [math]O(\log)[/math] времени. Пусть [math]m = \sum_

[/math] . Тогда время работы алгоритма — [math]O(m\log)[/math]

Покажем, что [math]m = O(n + I)[/math] , где [math]I[/math] — количество пересечений. Для этого рассмотрим планарный граф, вершинами которого являются концы отрезков, а также их точки пересечения, а ребрами — части отрезков, их соединяющие. Рассмотрим событие [math]p[/math] . Ему соответствует вершина графа со степенью [math]O(m(p))[/math] , следовательно [math]m = O(\sum_

) = O(E) = O(V) = O(2n + I)[/math] , где [math]deg(p)[/math] — степень [math]p[/math] , [math]E[/math] — число ребер в графе, [math]V[/math] — число вершин. (Предпоследний переход следует из формулы Эйлера.)

Объём памяти

Очевидно, что статус в худшем случае занимает [math]O(n)[/math] памяти, однако очередь событий может занимать [math]O(n + I)[/math] памяти. Если модифицировать алгоритм так, что в очереди будут храниться только точки пересечения отрезков, соседних в статусе, то объём используемой памяти сократится до [math]O(n)[/math] . Для этого нужно удалять точки пересечения отрезков, которые перестали быть соседними. Перед тем, как мы дойдём до точки удаленной точки, обязательно найдётся соседняя в статусе пара отрезков, которые пересекаются в этой точке, и она снова будет вставлена в очередь. Ясно, что такая оптимизация не влияет на время работы алгоритма.

Источники

  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 2: Line Segment Intersection: pp.20–29.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *