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