Второй подход опирается на математический анализ алгоритмов, независимый от конкретной реализации и входных данных. Рассмотрим этот подход на приведенном ниже примере программы, которая вычисляет сумму последовательности чисел (листинг А. 1).

Листинг А. 1. Программа вычисления суммы последовательности чисел

Первый этап анализа состоит в том, что создается определенное абстрактное представление входных данных, позволяющее найти какой-то параметр (или параметры), который характеризует объем входных данных. В рассматриваемом примере объем входных данных можно охарактеризовать с помощью такого параметра, как длина последовательности, которая будет обозначаться как п. На втором этапе необходимо определить абстрактное представление реализации и найти какой-то критерий, отражающий продолжительность прогона алгоритма, но не привязанный к конкретному компилятору или компьютеру. Применительно к программе Summation этим критерием может служить количество строк выполняемого кода; кроме того, данный критерий может быть более детализированным и измеряющим количество сложений, присваиваний, обращений к элементам массивов, а также ветвлений, выполняемых в этом алгоритме. В любом случае будет получена характеристика общего количества шагов, выполняемых алгоритмом, как функция от объема входных данных. Обозначим эту характеристику как т[п). Если за основу берется количество строк кода, то в данном примере Т[п) =2п+2.

Если бы все программы были такими же простыми, как Summation, то область анализа алгоритмов не заслуживала бы названия научной. Но исследования в этой области существенно усложняются из-за наличия двух проблем. Первая проблема заключается в том, что редко удается найти параметр, подобный т(п), который полностью характеризует количество шагов, выполняемых в алгоритме. Вместо этого обычно можно самое большее вычислить этот показатель для наихудшего случаяили для среднего случая. А для вычисления среднего требуется, чтобы аналитик принял какие-то обоснованные предположения по распределению наборов входных данных.