Последовательность действий алгоритма определяется не в последнюю очередь входными данными.
Некоторые алгоритмы сортировки могут работать очень быстро, если входной список уже отсортирован, тогда как другие алгоритмы покажут весьма скромный результат на таком списке. А вот на случайном списке результат может оказаться противоположным.
Нельзя ограничиваться анализом поведения алгоритмов на одном входном наборе данных. Нужно искать такие данные, которые обеспечивают как самое быстрое, так и самое медленное выполнение алгоритма. Кроме того, нужно оценивать и среднюю эффективность алгоритма на всех возможных наборах данных.
При анализе необходимо рассматривать все типы возможных множеств входных значений, поскольку если ограничиться одним множеством, оно может оказаться тем самым, на котором решение самое быстрое (или самое медленное). В результате мы получим ложное представление об алгоритме.
Разбиение различных входных множеств на классы в зависимости от поведения алгоритма на каждом множестве, позволяет уменьшить количество рассматриваемых ситуаций.
Если список упорядочен в порядке убывания, то перед началом цикла будет сделано одно присваивание, а в теле цикла присваиваний не будет. Если список упорядочен по возрастанию, то всего будет сделано N присваиваний (одно перед началом цикла и N - 1 в цикле).
Число различных расстановок 10 различных чисел в списке есть 10! = 3 628 800. Имеется 362 800 входных множеств, у которых первое число является наибольшим; их все можно поместить в один класс. Если наибольшее по величине число стоит на втором месте, то алгоритм сделает ровно два присваивания. Множеств, в которых наибольшее по величине число стоит на втором месте, 362 800. Их можно отнести к другому классу. Видно, как будет меняться число присваиваний при изменении положения наибольшего числа от 1 до N. Таким образом, мы должны разбить все входные множества на N разных классов по числу сделанных присваиваний. Нет необходимости выписывать или описывать детально все множества, помещенные в каждый класс. Нужно знать лишь количество классов и объём работы на каждом множестве класса.
Число возможных наборов входных данных может стать очень большим при увеличении N. Например, 10 различных чисел можно расположить в списке 3 628 800 способами. Невозможно рассмотреть все эти способы. Вместо этого мы разбиваем списки на классы в зависимости от того, что будет делать алгоритм. Для вышеуказанного алгоритма разбиение основывается на местоположении наибольшего значения. В результате получается 10 разных классов. Для другого алгоритма, например алгоритма поиска наибольшего и наименьшего значения, наше разбиение могло бы основываться на том, где располагаются наибольшее и наименьшее значения. В таком разбиении 90 классов. Как только мы выделили классы, мы можем посмотреть на поведение алгоритма на одном множестве из каждого класса. Если классы выбраны правильно, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций скорее всего будет другим.
Если нам известно, что число различных возможных значений входа в точности равно 10, то мы можем с уверенностью сказать, что вероятность каждого такого входа заключена между 0 и 1, и что сумма всех этих вероятностей равна 1, поскольку один из них наверняка должен быть реализован. Если возможности каждого из входов одинаковы, то вероятность каждого из них равна 0,1 (один из 10, или 1/10).
По большей части анализ заключается в описании всех возможностей, а затем мы будем предполагать, что все они равновероятны. Если общее число возможностей равно N, то вероятность реализации каждой из них равна 1/N.
Некоторые алгоритмы сортировки могут работать очень быстро, если входной список уже отсортирован, тогда как другие алгоритмы покажут весьма скромный результат на таком списке. А вот на случайном списке результат может оказаться противоположным.
Нельзя ограничиваться анализом поведения алгоритмов на одном входном наборе данных. Нужно искать такие данные, которые обеспечивают как самое быстрое, так и самое медленное выполнение алгоритма. Кроме того, нужно оценивать и среднюю эффективность алгоритма на всех возможных наборах данных.
При анализе необходимо рассматривать все типы возможных множеств входных значений, поскольку если ограничиться одним множеством, оно может оказаться тем самым, на котором решение самое быстрое (или самое медленное). В результате мы получим ложное представление об алгоритме.
Разбиение различных входных множеств на классы в зависимости от поведения алгоритма на каждом множестве, позволяет уменьшить количество рассматриваемых ситуаций.
Алгоритм поиска наибольшего элемента в списке из N элементов
Рассмотрим, например, алгоритм поиска наибольшего элемента в списке из N элементов:Если список упорядочен в порядке убывания, то перед началом цикла будет сделано одно присваивание, а в теле цикла присваиваний не будет. Если список упорядочен по возрастанию, то всего будет сделано N присваиваний (одно перед началом цикла и N - 1 в цикле).
Число различных расстановок 10 различных чисел в списке есть 10! = 3 628 800. Имеется 362 800 входных множеств, у которых первое число является наибольшим; их все можно поместить в один класс. Если наибольшее по величине число стоит на втором месте, то алгоритм сделает ровно два присваивания. Множеств, в которых наибольшее по величине число стоит на втором месте, 362 800. Их можно отнести к другому классу. Видно, как будет меняться число присваиваний при изменении положения наибольшего числа от 1 до N. Таким образом, мы должны разбить все входные множества на N разных классов по числу сделанных присваиваний. Нет необходимости выписывать или описывать детально все множества, помещенные в каждый класс. Нужно знать лишь количество классов и объём работы на каждом множестве класса.
Число возможных наборов входных данных может стать очень большим при увеличении N. Например, 10 различных чисел можно расположить в списке 3 628 800 способами. Невозможно рассмотреть все эти способы. Вместо этого мы разбиваем списки на классы в зависимости от того, что будет делать алгоритм. Для вышеуказанного алгоритма разбиение основывается на местоположении наибольшего значения. В результате получается 10 разных классов. Для другого алгоритма, например алгоритма поиска наибольшего и наименьшего значения, наше разбиение могло бы основываться на том, где располагаются наибольшее и наименьшее значения. В таком разбиении 90 классов. Как только мы выделили классы, мы можем посмотреть на поведение алгоритма на одном множестве из каждого класса. Если классы выбраны правильно, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций скорее всего будет другим.
Вероятности
Алгоритмы анализируются в зависимости от входных данных, а для этого необходимо оценивать, насколько часто встречаются те или иные наборы входных данных. Вероятность того, что входные данные удовлетворяют тем или иным условиям представляет собой число в интервале между нулем и единицей. Вероятность 0 того или иного события означает, что событие не произойдёт никогда, а вероятность 1 - что оно произойдёт наверняка.Если нам известно, что число различных возможных значений входа в точности равно 10, то мы можем с уверенностью сказать, что вероятность каждого такого входа заключена между 0 и 1, и что сумма всех этих вероятностей равна 1, поскольку один из них наверняка должен быть реализован. Если возможности каждого из входов одинаковы, то вероятность каждого из них равна 0,1 (один из 10, или 1/10).
По большей части анализ заключается в описании всех возможностей, а затем мы будем предполагать, что все они равновероятны. Если общее число возможностей равно N, то вероятность реализации каждой из них равна 1/N.
Комментарии
Отправить комментарий