При анализе алгоритмов вероятностный анализ алгоритмов — это подход к оценке вычислительной сложности алгоритма или вычислительной задачи. Он начинается с предположения о вероятностном распределении набора всех возможных входных данных. Затем это предположение используется для разработки эффективного алгоритма или для определения сложности известного алгоритма. Этот подход отличается от вероятностных алгоритмов , но их можно комбинировать.
Для невероятностных, а точнее детерминированных алгоритмов, наиболее распространенными типами оценок сложности являются средняя сложность и почти всегда сложность. Чтобы получить среднюю сложность, при заданном входном распределении оценивается ожидаемое время алгоритма, тогда как для оценки почти всегда сложности оценивается, что алгоритм допускает данную оценку сложности, которая почти наверняка выполняется.
При вероятностном анализе вероятностных (рандомизированных) алгоритмов в дополнение к входным распределениям также учитываются распределения или средние значения всех возможных выборов в рандомизированных шагах.
Эта статья, связанная с алгоритмами или структурами данных , является незавершенной . Вы можете помочь Википедии, дополнив ее .