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