double arrow

Элементы теории сложности

Односторонние функции

Если схема зависит от некоторого параметра, который определяет данные (n)

=> Tφ(n) – время; Sφ(n) – объем памяти.

φ – некоторый вычислительный алгоритм.

φ зависит от n – определенный объем входных данных.

=> Tφ(n), Sφ(n).

Алгоритм сложения:

a, b длины n бит, с=а+b длины n+1 бит.

1) d=c;

2) для i=0…n-1;

3) ci=Low(ai+bi+d);

4) d=High(ai+bi+d);

5) cn=d.

Tφ(a,b,n)=n, Sφ(a,b,n)=3n+1,

=> Tслож(n)=n, Sслож(n)=3n+1=О(n).

Для определения сложности алгоритма свяжем с понятием заданное число, называемое ее размером, который выражает меру количества входных данных.

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

Алгоритм умножения:

c=a*b,

где a,b – n бит, с – 2n бит.

1) с=0;

2) для i=0…n-1

3) если аi≠0;

4) c=c+b*2i.

Tумн(a,b,n)=ω(a)*Тслож(n),

где ω(a) – количество единиц в числе a (вес).

В зависимости от требований в качестве временной сложности алгоритма может рассматриваться минимальное, среднее, максимальное время алгоритма.

;

;

.

Среднее время:

=>

Алгоритм возведения в степень:

c=ab(modN), где a,b,N,c – n бит.

1) с=1;

2) для i=n-1…0

3) c=c2(modN);

4) если bi=1, то

5) с=с*a(modN).

Tдел(n)=сn2, Tmod(n)=сn2, Tmod умн(n)=с1n2;

Среднее время:,

По теории сложности принято исследовать асимптотическое поведение вычислительной сложности от размера задачи.

f(n) и g(n) – функции.

Говорят, что f(n)=O(g(n)) при n→∞, если существуют n0, C такие что при любых n>n0,.

Если,

=>.

O(g) ≡ величина порядка g.

Говорят, что алгоритм φ имеет полиномиальную сложность, если:

, где p(n) – полином.

Линейная сложность:

Квадратичная сложность:

Кубическая сложность:

Алгоритм имеет экспоненциальную сложность если: (ap(n)),

где, a>1 – константа, p(n) – полином.

Если алгоритм быстрее O(ap(n)) и медленнее O(p(n)), то называется задачей субэкспоненциальной сложности,

.

Пример: n=106, скорость 106 операций/сек.

Класс Сложность Количество операций Время (106 бит/сек)
Линейная O(n) 106 1 cек
Квадратичная O(n2) 1012 10 дней
Кубическая O(n3) 1018 27397 лет
Субэкспоненциальная   21000 3∙1052 лет
Экспоненциальная O(2n) 10301030 10301016 лет

При 106 процессоров:

Класс Сложность Количество операций Время (106 бит/сек)
Линейная O(n) 106 10-6 cек
Квадратичная O(n2) 1012 1 сек
Кубическая O(n3) 1018 10 дней
Субэкспоненциальная   21000 10282 лет
Экспоненциальная O(2n) 10301030 10301016 лет

Говорят что алгоритм простой, если его вычислительная сложность Tφ(n) полиномиальная.

Сложный, если неполиномиальный.

Задача простая, если существует простой алгоритм φ, сложная если все алгоритмы φ сложные.

Модель теории сложности используется для выбора алгоритма и выбора параметров алгоритма.

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

Сложными алгоритмами называют алгоритмы, чьи вычислительные сложности не превышают допустимые пределы.

Пример:

1) Сложение чисел:

Tслож(n)=O(n) – простая задача.

2) Умножение, деление чисел:

Tумн(n)=O(n2) – простая задача.

3) Возведение в степень:

Tстеп(n)=O(n3) – простая задача.

4) Решение системы линейных уравнений методом Гаусса:

T(n)=O(n3) – простая задача.

5) Задача об «укладке ранца», S={S1,…,Sn}, e=Si1+…+Sim, требуется найти {Si1,…,Sim}. Алгоритм: полный перебор (ΣSij);

T(n)=O(2n) – сложная задача.

6) Задача разложения на сомножители (задача факторизации): - задача субэкспоненциальной сложности.

7) Задача нахождения показателя степени по известным y, a и p называется задачей дискретного логарифмирования: y=ax(modp). Наиболее эффективный алгоритм требует, где n – количество битов в числе р;

– сложная задача.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: