Рубрики

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

Что такое рандомизированный алгоритм?

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

Как анализировать рандомизированные алгоритмы?

Некоторые рандомизированные алгоритмы имеют детерминированную временную сложность. Например, эта реализация алгоритма Каргера имеет временную сложность как 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

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

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

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

0.00 (0%) 0 votes