Полиномиальное оценивание сложности алгоритмов

Традиционные записи алгоритмов в форме последовательных программ, математических формул и т.п. зависят, как правило, от внешних переменных, которые определяют “размеры” алгоритмов и значения которых не известны до начала их реализации. Процесс преобразования таких записей к виду, удобному для реализации на параллельных вычислительных системах, очень сложен. Поэтому желательно иметь метод предварительного оценивания сложности алгоритма как функции неизвестных переменных. В настоящей статье описывается один из подобных методов. Он позволяет полиномиально оценить параллельную сложность любого алгоритма, записанного в форме последовательной программы из так называемого линейного класса. Метод не требует какой-либо информации о структуре алгоритма и основан только на анализе текста программы.