Ожидаемое время работы в рандомизированном алгоритме

Question

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

При использовании рандомизированного алгоритма конкретный вход больше не важный. Случайные числа важны, и мы можем получить ожидаемое время выполнения, где мы теперь усредняем по всем возможным случайным числа вместо всех возможных входов. Использование быстрой сортировки с Случайный поворот дает алгоритм O (n log n) с ожидаемым временем. Это означает что для любого ввода, включая уже отсортированный ввод, время выполнения ожидается, что будет O (n log n), основываясь на статистике случайных номера. Ожидаемое время выполнения несколько сильнее, чем средний случай, но, конечно, слабее, чем соответствующий предел наихудшего случая.

Сначала мы увидим новую схему поддержки бинарного поиска дерева операций в O (log n) ожидаемое время. Еще раз, это означает, что нет плохих входных данных, просто плохие случайные числа. Из теоретического С точки зрения, это не очень интересно, так как сбалансированный поиск деревья достигают этой границы в худшем случае. Тем не менее, использование рандомизация приводит к относительно простым алгоритмам поиска, вставка, и особенно удаление.

Мой вопрос к тексту выше

1. Что автор имеет в виду под «ожидаемой оценкой времени выполнения, которая несколько сильнее, чем оценка среднего случая, но, конечно, она слабее, чем соответствующая оценка наихудшего случая»? в тексте выше.

2. Пересмотр бинарных деревьев поиска, что автор имел в виду, «поскольку сбалансированные деревья поиска достигают этой границы в худшем случае»? В моем понимании для двоичных деревьев поиска наихудший случай - это O (d), где d - глубина узла, это может быть "N", то есть O (N). что автор имеет в виду под этим, как наихудший случай выше?

Спасибо!

Answer 1

1. Как автор объяснил в предложении ранее: ожидаемое время должно сохраняться для любого ввода.Средний регистр усредняется по всем входным данным, то есть вы получаете достаточно посредственный вход.Ожидаемое время означает, что независимо от того, насколько плохим является входное значение, алгоритм должен иметь возможность вычислять его в пределах границ, если бог случайных чисел хорош (т.е. дает вам ожидаемое значение, а не худшую возможную вещь, как она часто делает).

2. Сбалансированный деревья бинарного поиска.Они не могут достичь глубины N, потому что они сбалансированы .

Answer 2

В рандомизированной быстрой сортировке, даже намеренно, мы не можем произвести неверный ввод (что может привести к наихудшему случаю), так как случайная перестановка делает порядок ввода неактуальным.Рандомизированный алгоритм работает плохо, только если генератор случайных чисел производит неудачную перестановку для сортировки. Почти все перестановки приводят к тому, что быстрая сортировка выполняется ближе к среднему случаю, очень мало перестановок, которые вызывают поведение, близкое к наихудшему, и, следовательно, вероятностьв худшем случае ввод очень низкий ... поэтому он почти работает в O (nlogn).

Answer 3

1. Автор означает, что в среднем быстрая сортировка будет давать более медленные результаты, чем O (n log n) (Это не правильно для всех алгоритмов сортировки, например, для ожидаемого времени сортировки слиянием == среднее время == O (n log) n) и рандомизация не требуется)

2. O (d) = O (log n) для сбалансированных деревьев

PS Кто автор?