Определение.

В случае, когда в качестве модели вычислений берутся неветвящиеся программы, говорят, что данная задача имеет временную и емкостную сложность O_A (f(n)), если найдется последовательность программ для ее решения с временной или емкостной сложностью не более cf(n) для некоторой постоянной c:

T  cf(n) , S  cf(n)

O_A (f(n)) читается: “порядка f(n) шагов неветвящейся программы”. Индекс А cнизу обозначает “арифметический” - это основная характеристика неветвящихся программ.

Таким образом, вычисление полинома имеет временную, а также емкостную сложность O_A (n).

O_A - арифметический равномерный критерий.

0.9. Неветвящиеся программы и логарифмический весовой критерий.

Равномерный весовой критерий применительно к неветвящимся программам годится, если этот вес имеет ”разумный” размер. Модификация модели ,соответствующая логарифмической весовой функции, называется битовым вычислением. Это та же неветвящаяся программа, но в ней

1) все переменные принимают значения 0 или 1, т.е. это биты,

2) используются логические операции вместо арифметических (набор команд для РАМ должен состоять из этих операций): and обозначается через , or - через , exclusive or - через , not – через ¬.

Для битовой модели арифметические операции над целыми числами i и j занимают по меньшей мере l(i)+l(j) шагов, что соответствует логарифмическому весу операндов. Действительно, умножение и деление с помощью наилучших известных алгоритмов для умножения и деления

i на j требуют более, чем l(i)+l(j) шагов.

При битовых вычислениях порядок величин обозначается через O_Б. Битовая модель полезна, когда речь идет об основных операциях, таких, как арифметические, которые исходны в других моделях. Например, для модели неветвящихся программ умножение двух n-разрядных чисел можно осуществить за O_A(1) шагов, тогда как для битовой модели наилучший известный результат – O_Б(n log n log log n) шагов.

0.10. Ветвления.

В некоторых задачах удобно в качестве основной меры сложности брать число выполняемых команд разветвления. Разумно рассматривать модель, в которой все шаги дают разветвления.

Обычно программу, состоящую из разветвлений, представляют в виде двоичного дерева, называемого деревом решений. Каждый внутренний узел представляет один из шагов решения.

В общем случае управление переходит от узла к одному из его сыновей, до тех пор пока не будет достигнут лист.

Пример.

Сортировка чисел.

Если рассматривается n чисел, то листов будет n На каждом шаге сравнения a<b<c можно попасть в одно из двух состояний. Программа получается без циклов.

Чтобы написать эффективный алгоритм, надо минимизировать максимальный путь. Эта схема будет , по возможности, сбалансированным бинарным деревом.

С ложность  lg n! ;

lg (n!)  O(n lg n)  сортировка чисел с помощью сравнения может быть сделана меньше, чем за n lg n.

0.11. Операции с двоичными векторами фиксированной длины. Определение.

Неотрицательные функции f₁(n) и f₂(n) полиномиально связаны (эквивалентны), если найдутся такие полиномы p₁(n) и p₂(n) , что для всех n справедливы неравенства :

f₁(n)  p₁(f₂(n)) и f₂(n)  p₂( f₁(n) ).

Но n² и 2ⁿ не являются полиномиально связанными, т.к. нет такого полинома p(x), что p(n²)2ⁿ

для всех n.

Это свойство является транзитивным и рефлексивным.

Пример.

n³ и n² lg n lg lg lg (n³+(sin n)² +2) - полиномиально эквивалентны.