Cтраница 4
В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. [46]
Основными характеристиками алгоритма решения такой системы являются точность решения, емкостная и временная сложность. Алгоритмы решения систем линейных уравнений разделяются на две большие группы. К первой относятся так называемые точные алгоритмы которые теоретически ( при бесконечной разрядной сетке: w - - оо) определяют точные значения неизвестных после конечного числа арифметических операций. Ко второй группе относятся итерационные алгоритмы, которые получают приближенное решение в результате неопределенного числа итерационных шагов. [47]
Рассмотрим подробнее процедуры реализации преобразований I и II и оценим их временную сложность. Пусть G - граф, над которым выполняется данное преобразование I или II, a G - граф, полученный из G в результате выполнения этого преобразования. [48]
Из такой тотальной полиномиальной замкнутости следует, что свойство иметь полиномиально ограниченную временную сложность является алгоритмическим свойством проблемы, не зависящим ( в разумных пределах) от выбора средств вычислений. В разных моделях меняются только характеристики полиномов - коэффициенты и степень. [49]
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. [50]
Таким образом, это побуждает нас использовать простую модель, для которой временная сложность задач полиномиально связана с их сложностью на РАМ. В частности, модель, которую мы будем применять, а именно многоленточная машина Тьюринга, может потребовать ( / ( п)) 4 шагов х), чтобы сделать то, что РАМ при логарифмической весовой функции делает за / ( п) шагов, но не больше. Итак, временные сложности на РАМ и машинах Тьюринга, как мы увидим, полиномиально связаны. [51]