Что такое рандомизированный алгоритм?
Алгоритм, который использует случайные числа, чтобы решить, что делать дальше в любом месте своей логики, называется рандомизированным алгоритмом. Например, в рандомизированной быстрой сортировке мы используем случайное число, чтобы выбрать следующий стержень (или мы случайным образом перемешиваем массив). И в алгоритме Каргера мы случайным образом выбираем грань.
Как анализировать рандомизированные алгоритмы?
Некоторые рандомизированные алгоритмы имеют детерминированную временную сложность. Например, эта реализация алгоритма Каргера имеет временную сложность как O (E). Такие алгоритмы называются алгоритмами Монте-Карло и их легче анализировать в худшем случае.
С другой стороны, временная сложность других рандомизированных алгоритмов (кроме Лас-Вегаса) зависит от значения случайной величины. Такие рандомизированные алгоритмы называются алгоритмами Лас-Вегаса . Эти алгоритмы обычно анализируются на ожидаемый наихудший случай. Чтобы вычислить ожидаемое время, взятое в наихудшем случае, все возможные значения используемой случайной величины необходимо учитывать в наихудшем случае, а время, которое требуется каждому возможному значению, необходимо оценить. Среднее из всех оцененных времен — ожидаемая сложность времени наихудшего случая. Ниже приведены факты, которые обычно полезны при анализе таких алгоритмов.
Линейность ожидания
Ожидаемое количество испытаний до успеха.
Например, рассмотрим ниже рандомизированную версию QuickSort.
Центральная ось — это ось, которая делит массив таким образом, что одна сторона имеет как минимум 1/4 элемента.
// Sorts an array arr[low..high]
randQuickSort(arr[], low, high)
1. If low >= high, then EXIT.
2. While pivot 'x' is not a Central Pivot.
(i) Choose uniformly at random a number from [low..high].
Let the randomly picked number number be x.
(ii) Count elements in arr[low..high] that are smaller
than arr[x]. Let this count be sc.
(iii) Count elements in arr[low..high] that are greater
than arr[x]. Let this count be gc.
(iv) Let n = (high-low+1). If sc >= n/4 and
gc >= n/4, then x is a central pivot.
3. Partition arr[low..high] around the pivot x.
4. // Recur for smaller elements
randQuickSort(arr, low, sc-1)
5. // Recur for greater elements
randQuickSort(arr, high-gc+1, high) Важным моментом в нашем анализе является то, что время, необходимое для выполнения шага 2, равно O (n).
Сколько раз цикл проходит перед тем, как найти центральный стержень?
Вероятность того, что случайно выбранный элемент является центральной осью, равна 1/2.
Таким образом, ожидаемое количество выполнений цикла while равно 2 (подробности см. В этом разделе).
Таким образом, ожидаемая временная сложность этапа 2 составляет O (n).
Какова общая сложность времени в худшем случае?
В худшем случае каждый раздел делит массив так, что одна сторона имеет n / 4 элемента, а другая сторона имеет 3n / 4 элемента. Наихудшая высота дерева рекурсии — Log 3/4 n, которая равна O (Log n).
Т (п)
Обратите внимание, что приведенный выше рандомизированный алгоритм - не лучший способ реализовать рандомизированную быструю сортировку. Идея здесь состоит в том, чтобы упростить анализ, поскольку он прост для анализа.
Как правило, рандомизированная быстрая сортировка осуществляется путем случайного выбора оси (без цикла). Или перетасовкой элементов массива. Ожидаемая сложность этого алгоритма в наихудшем случае также составляет O (n Log n), но анализ сложен, сам профессор MIT упоминает то же самое в своей лекции здесь .Рандомизированные алгоритмы | Комплект 2 (Классификация и приложения)
Ссылки:
http://www.tcs.tifr.res.in/~workshop/nitrkl_igga/randomized-lecture.pdfЭта статья предоставлена Ашишем Шармой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Рандомизированные алгоритмы | Комплект 2 (Классификация и приложения)
- Рандомизированные алгоритмы | Набор 3 (1/2 Приблизительная Медиана)
- Рандомизированные алгоритмы | Установите 0 (математическое обоснование)
- Рандомизированный алгоритм двоичного поиска
- Балансировка нагрузки на серверах (рандомизированный алгоритм)
- Алгоритм Каргера для минимального разреза | Набор 2 (анализ и приложения)
- Алгоритм Каргера для минимального разреза | Комплект 1 (Введение и реализация)
- Максимальное строковое разделение
- Подмассив максимальной длины, который удовлетворяет заданным условиям
- Генерация случайной перестановки от 1 до N
- Генерация случайной строки с использованием PHP
- Генерация OTP (одноразового пароля) в PHP
- Перемешать или рандомизировать список в Java
- Середина хеширования
0.00 (0%) 0 votes