Мы собираемся анализировать алгоритмы в зависимости от входных данных, а для этого нам необходимо оценивать, насколько часто встречаются те или иные наборы входных данных. Тем самым, нам придется работать с вероятностями того, что входные данные удовлетворяют тем или иным условиям.
Вероятность того или иного события представляет собой число в интервале между нулем и единицей, причем вероятность 0 означает, что событие не произойдет никогда, а вероятность 1 - что оно произойдет наверняка.
Если нам известно, что число различных возможных значений входа в точности равно 10, то мы можем с уверенностью сказать, что вероятность каждого такого входа заключена между 0 и 1, и что сумма всех этих вероятностей равна 1, поскольку один из них наверняка должен быть реализован. Если возможности реализации каждого из входов одинаковы, то вероятность каждого из них равна 0,1 (один из 10, или 1/10).
По большей части, наш анализ будет заключаться в описании всех возможностей, а затем мы будем предполагать, что все они равновероятны. Если общее число возможностей равно N, то вероятность реализации каждой из них равна 1/N.
