Вероятностный анализ алгоритмов
В анализе алгоритмов вероятностный анализ алгоритмов — это подход к оценке вычислительной сложности алгоритма или вычислительной проблемы. Он начинается с предположения о вероятностном распределении набора всех возможных входных данных. Это предположение затем используется для разработки эффективного алгоритма или для вывода сложности известного алгоритма. Этот подход не такой же, как у вероятностных алгоритмов , но их можно объединить.
Для не вероятностных, а точнее детерминированных , алгоритмов наиболее распространенными типами оценок сложности являются сложность в среднем случае и сложность почти всегда. Чтобы получить сложность в среднем случае, учитывая входное распределение, оценивается ожидаемое время алгоритма, тогда как для оценки сложности почти всегда оценивается, что алгоритм допускает заданную оценку сложности, которая почти наверняка выполняется.
При вероятностном анализе вероятностных (рандомизированных) алгоритмов в дополнение к входным распределениям также учитываются распределения или средние значения всех возможных выборов на рандомизированных шагах.
Смотрите также
- Амортизированный анализ
- Средняя сложность случая
- Лучший, худший и средний случай
- Случайная самоприводимость
- Принцип отложенного решения
Ссылки
- Frieze, Alan M.; Reed, Bruce (1998), «Вероятностный анализ алгоритмов», в Habib, Michel; McDiarmid, Colin; Ramirez-Alfonsin, Jorge; Reed, Bruce (ред.), Вероятностные методы для алгоритмической дискретной математики , Алгоритмы и комбинаторика, т. 16, Springer, стр. 36–92 , doi :10.1007/978-3-662-12788-9_2, ISBN 9783662127889
- Хофри, Миха (1987), Вероятностный анализ алгоритмов: О вычислительных методологиях для оценки производительности компьютерных алгоритмов , Springer, doi : 10.1007/978-1-4612-4800-2, ISBN 9781461248002
- Frieze, AM (1990), «Вероятностный анализ графовых алгоритмов», в Tinhofer, G.; Mayr, E.; Noltemeier, H.; Syslo, MM (ред.), Computational Graph Theory , Computing Supplementa, т. 7, Springer, стр. 209–233 , doi :10.1007/978-3-7091-9076-0_11, ISBN 9783709190760
 | Эта статья по теме алгоритмы или структуры данных является заглушкой . Вы можете помочь Википедии, расширив ее. |
