Вероятностный анализ алгоритмов

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

Для невероятностных, точнее, детерминированных алгоритмов наиболее распространенными типами оценок сложности являются сложность в среднем случае и сложность почти всегда. Чтобы получить среднюю сложность при заданном входном распределении, оценивается ожидаемое время алгоритма, тогда как для почти всегда оценки сложности оценивается, что алгоритм допускает заданную оценку сложности, которая почти наверняка выполняется.

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

См. также

Ссылки

Фриз, Алан М.; Рид, Брюс (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, doi : 10.1007/978-3-7091-9076-0_11 , ISBN. 9783709190760

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