Рубрики

Рандомизированные алгоритмы | Комплект 2 (Классификация и приложения)

Мы настоятельно рекомендуем ссылаться на этот пост ниже.

Рандомизированные алгоритмы | Комплект 1 (Введение и анализ)

классификация

Рандомизированные алгоритмы подразделяются на две категории.

Лас-Вегас: эти алгоритмы всегда дают правильный или оптимальный результат. Временная сложность этих алгоритмов основана на случайном значении, а временная сложность оценивается как ожидаемое значение. Например, рандомизированная быстрая сортировка всегда сортирует входной массив, и ожидаемая сложность быстрой сортировки по времени в наихудшем случае равна O (nLogn) .

Монте-Карло: Дайте правильный или оптимальный результат с некоторой вероятностью. Эти алгоритмы имеют детерминированное время выполнения, и обычно легче определить сложность времени наихудшего случая. Например, эта реализация алгоритма Каргера производит минимальное сокращение с вероятностью, большей или равной 1 / n 2 (n — количество вершин), и имеет сложность времени наихудшего случая как O (E). Другим примером является метод Фермет для тестирования первичности .

Пример для понимания классификации:

Consider a binary array where exactly half elements are 0
and half are 1. The task is to find index of any 1.  

Алгоритм Лас-Вегаса для этой задачи состоит в том, чтобы продолжать выбирать случайный элемент, пока мы не найдем 1. Алгоритм Монте-Карло для того же самого состоит в том, чтобы продолжать выбирать случайный элемент, пока мы не найдем 1 или не попробуем максимально допустимое время, скажем, k.
Алгоритм Лас-Вегаса всегда находит индекс 1, но сложность времени определяется как ожидаемое значение. Ожидаемое количество испытаний до успеха равно 2, поэтому ожидаемая сложность по времени составляет O (1).
Алгоритм Монте-Карло находит 1 с вероятностью [1 — (1/2) k ]. Временная сложность Монте-Карло составляет O (k), которая является детерминированной

Области применения и сфера применения:

  • Рассмотрим инструмент, который в основном выполняет сортировку. Позвольте инструменту быть использованным многими пользователями, и есть немного пользователей, которые всегда используют инструмент для уже отсортированного массива. Если инструмент использует простую (не рандомизированную) быструю сортировку, то эти немногие пользователи всегда сталкиваются с наихудшей ситуацией. С другой стороны, если инструмент использует рандомизированную быструю сортировку, то нет пользователя, который всегда получает худший случай. Все получают ожидаемое время.
  • Рандомизированные алгоритмы имеют огромное применение в криптографии.
  • Балансировка нагрузки .
  • Теоретико-числовые приложения: тестирование простоты
  • Структуры данных: хеширование, сортировка, поиск, статистика заказов и вычислительная геометрия.
  • Алгебраические тождества: проверка полиномиальной и матричной тождественности . Интерактивные системы доказательств.
  • Математическое программирование: более быстрые алгоритмы линейного программирования, округление линейных программных решений до целочисленных программных решений
  • Алгоритмы графа: минимальные остовные деревья, кратчайшие пути, минимальные срезы .
  • Подсчет и перечисление: Матрица постоянных Подсчет комбинаторных структур.
  • Параллельные и распределенные вычисления: распределенный консенсус по предотвращению тупиков
  • Вероятностные доказательства существования. Покажите, что комбинаторный объект возникает с ненулевой вероятностью среди объектов, взятых из подходящего вероятностного пространства.
  • Дерандомизация: сначала разработайте рандомизированный алгоритм, а затем утверждайте, что он может быть дерандомизирован для получения детерминированного алгоритма.

Источники:
http://theory.stanford.edu/people/pragh/amstalk.pdf
https://en.wikipedia.org/wiki/Randomized_algorithm

Эта статья предоставлена Ашишем Шармой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Рандомизированные алгоритмы | Комплект 2 (Классификация и приложения)

0.00 (0%) 0 votes