 | В этой статье не процитировать какие - либо источники . ( апрель 2021 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В анализе алгоритмов , вероятностный анализ алгоритмов представляет собой подход , чтобы оценить вычислительную сложность в качестве алгоритма или вычислительной задачи. Он начинается с предположения о вероятностном распределении набора всех возможных входных данных. Это предположение затем используется для разработки эффективного алгоритма или для определения сложности известного алгоритма. Этот подход отличается от подхода вероятностных алгоритмов , но их можно комбинировать.
Для не вероятностных, а точнее детерминированных алгоритмов наиболее распространенными типами оценок сложности являются средняя сложность и почти всегда сложность. Чтобы получить среднюю сложность, учитывая входное распределение, оценивается ожидаемое время алгоритма, тогда как для почти всегда оценки сложности оценивается, что алгоритм допускает данную оценку сложности, которая почти наверняка выполняется.
В вероятностном анализе вероятностных (рандомизированных) алгоритмов, помимо входных распределений, также принимаются во внимание распределения или среднее значение всех возможных выборов на рандомизированных шагах.
См. Также [ править ]
- Амортизированный анализ
- Средняя сложность
- Лучший, худший и средний случай
- Случайная самовосстановление
- Принцип отложенного решения
 | Эта статья, посвященная алгоритмам или структурам данных, является незавершенной . Вы можете помочь Википедии, расширив ее . |
