Вероятностный анализ алгоритмов
В анализе алгоритмов вероятностный анализ алгоритмов подход к оценке вычислительной сложности алгоритма — это или вычислительной задачи. Все начинается с предположения о вероятностном распределении набора всех возможных входных данных. Это предположение затем используется для разработки эффективного алгоритма или для определения сложности известного алгоритма. Этот подход отличается от подхода вероятностных алгоритмов , но их можно комбинировать.
Для невероятностных, точнее , детерминированных алгоритмов наиболее распространенными типами оценок сложности являются сложность в среднем случае и сложность почти всегда. Чтобы получить среднюю сложность при заданном входном распределении, оценивается ожидаемое время алгоритма, тогда как для почти всегда оценки сложности оценивается, что алгоритм допускает заданную оценку сложности, которая почти наверняка выполняется.
В вероятностном анализе вероятностных (рандомизированных) алгоритмов помимо входных распределений также учитываются распределения или среднее всех возможных выборов на рандомизированных шагах.
См. также [ править ]
- Амортизированный анализ
- Средняя сложность
- Лучший, худший и средний случай
- Случайная самоприводимость
- Принцип отложенного решения
Ссылки [ править ]
- Фриз, Алан М.; Рид, Брюс (1998), «Вероятностный анализ алгоритмов», Хабиб, Мишель; МакДиармид, Колин; Рамирес-Альфонсин, Хорхе; Рид, Брюс (ред.), Вероятностные методы для алгоритмической дискретной математики , алгоритмы и комбинаторика, том. 16, Спрингер, стр. 36–92, номер документа : 10.1007/978-3-662-12788-9_2 , ISBN. 9783662127889
- Хофри, Миха (1987), Вероятностный анализ алгоритмов: вычислительные методологии для оценки производительности компьютерных алгоритмов , Springer, doi : 10.1007/978-1-4612-4800-2 , ISBN 9781461248002
- Фриз, А.М. (1990), «Вероятностный анализ графовых алгоритмов», Тинхофер, Г.; Майр, Э.; Нольтемайер, Х.; Сысло, М.М. (ред.), Вычислительная теория графов , Computing Supplementa, vol. 7, Springer, стр. 209–233, номер документа : 10.1007/978-3-7091-9076-0_11 , ISBN. 9783709190760
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |