Иногда ожидаемое время работы означает среднее время работы для случайно выбранного входа.Но если это рандомизированный алгоритм, то часто подразумевается ожидаемое время выполнения в отношении случайных выборов, сделанных алгоритмом для каждого входа.Вот что здесь подразумевается.Для каждого ввода из n элементов рандомизированная быстрая сортировка выполняется в среднем за время O (n (log n)), усредненная только по броскам монет.
В этом ограниченном смысле ожидаемое время выполненияочень оправданная мера времени работы рандомизированного алгоритма.Если вас беспокоит только худшее, что может произойти, когда алгоритм переворачивает монеты внутри, тогда зачем вообще переворачивать монеты?С таким же успехом вы можете сделать их головы.(Что в случае рандомизированной быстрой сортировки уменьшило бы ее до обычной быстрой сортировки.)
Среднее значение по сравнению с наихудшим случаем является гораздо более серьезным вопросом, когда оно является средним по входным данным, а не средним по броскам монет.В этом случае среднее время выполнения в лучшем случае является цифрой, которая не адаптируется к изменениям в типе входных данных - различные варианты использования алгоритма могут иметь различные распределения входных данных.Я говорю в лучшем случае, потому что вы, возможно, не знаете, что гипотетическое распределение входных данных всегда является истинным использованием.
Глядя на наихудший случай в отношении бросков монет, имеет смысл только тогда, когда вы оба хотели бы бежать быстро, когда вашброски монет не неудачны, и не бегают слишком медленно, даже когда броски монет неудачны.Например, представьте, что вам нужен алгоритм сортировки для регулятора подачи кислорода (для медицинского пациента или аквалангиста).Тогда рандомизированная быстрая сортировка будет иметь смысл, только если вы оба хотите, чтобы результат был обычно очень быстрым, для удобства пользователя, И если худший случай не задушит пользователя, несмотря ни на что.Это надуманный сценарий для алгоритмов сортировки, потому что существуют неслучайные алгоритмы сортировки (такие как сортировка слиянием), которые не намного медленнее, чем быстрая сортировка в среднем.Он менее изобретателен для такой задачи, как тестирование на простоту, когда рандомизированные алгоритмы на намного быстрее, чем нерандомизированные алгоритмы.Тогда вы можете захотеть запустить его с помощью рандомизированного алгоритма - и в то же время запустить нерандомизированный алгоритм в качестве резервной копии.
(Хорошо, вы можете задаться вопросом, почему регулятор кислорода захочетчтобы узнать, являются ли определенные числа простыми числами. Может быть, для связи с медицинской компьютерной сетью требуется связь, и для обеспечения конфиденциальности медицинских данных эта связь должна быть безопасной ...)