Функция рандомизации - Randomization function

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

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

Использует

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

Например, рассмотрим алгоритм сортировки подобно быстрая сортировка, который имеет небольшое ожидаемое время выполнения, когда входные элементы представлены в случайном порядке, но очень медленно, когда они представлены в определенных неблагоприятных порядках. Функция рандомизации от целых чисел от 1 до п к целым числам от 1 до п можно использовать для перестановки п вводить элементы в «случайном» порядке перед вызовом этого алгоритма. Этот модифицированный (рандомизированный) алгоритм будет иметь небольшое ожидаемое время работы независимо от порядка ввода.

Случайность

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

На практике, однако, основная проблема заключается в том, что некоторые «плохие» случаи для детерминированного алгоритма могут встречаться на практике гораздо чаще, чем можно было бы спрогнозировать. Например, в наивном варианте быстрой сортировки наихудший случай - это когда элементы ввода уже отсортированы, что очень часто встречается во многих приложениях. Для таких алгоритмов может быть достаточно даже фиксированной псевдослучайной перестановки. Даже несмотря на то, что результирующий «псевдослучайный» алгоритм по-прежнему будет иметь столько же «плохих» случаев, как и исходный, они будут иметь определенные особые порядки, которые вряд ли возникнут в реальных приложениях. Итак, на практике часто используются функции рандомизации, производные от генераторы псевдослучайных чисел предпочтительно засеянный с внешними "случайными" данными, такими как время запуска программы.

Единообразие

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

Рекомендации