Вероятностный анализ алгоритмов - Probabilistic analysis of algorithms

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

Этот подход отличается от подхода вероятностные алгоритмы, но их можно сочетать.

Для не вероятностных, а именно детерминированный, алгоритмов, наиболее распространенными видами оценок сложности являются средняя сложность (ожидаемая временная сложность)^{[сомнительный ]} и почти всегда сложность. Чтобы получить среднюю сложность с учетом входного распределения, оценивается ожидаемое время алгоритма, тогда как для почти всегда оценки сложности оценивается, что алгоритм допускает данную оценку сложности, которая почти наверняка держит.

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

Смотрите также

• Амортизированный анализ
• Средняя сложность
• Лучший, худший и средний случай
• Случайная самовосстановление
• Принцип отложенного решения