Примерное время работы от сложности алгоритма. Виды функции сложности алгоритмов

Традиционно принято оценивать степень сложности алгоритма по объему используемых им основных ресурсов компьютера: процессорного времени и оперативной памяти. В связи с этим вводятся такие понятия, как временная сложность алгоритма и объемная сложность алгоритма.

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

Объемная сложность программы становится критической, когда объем обрабатываемых данных оказывается на пределе объема оперативной памяти ЭВМ. На современных компьютерах острота этой проблемы снижается благодаря как росту объема ОЗУ, так и эффективному использованию многоуровневой системы запоминающих устройств. Программе оказывается доступной очень большая, практически неограниченная область памяти (виртуальная память). Недостаток основной памяти приводит лишь к некоторому замедлению работы из-за обменов с диском. Используются приемы, позволяющие минимизировать потери времени при таком обмене. Это использование кэш-памяти и аппаратного просмотра команд программы на требуемое число ходов вперед, что позволяет заблаговременно переносить с диска в основную память нужные значения. Исходя из сказанного можно заключить, что минимизация емкостной сложности не является первоочередной задачей. Поэтому в дальнейшем мы будем интересоваться в основном временной сложностью алгоритмов.

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

Как правило, временная сложность алгоритма зависит от исходных данных. Это может быть зависимость как от величины исходных данных, так и от их объема. Если обозначить значение параметра временной сложности алгоритма α символом Tα, а буквой V обозначить некоторый числовой параметр, характеризующий исходные данные, то временную сложность можно представить как функцию Tα(V). Выбор параметра V зависит от решаемой задачи или от вида используемого алгоритма для решения данной задачи.

Пример 1. Оценим временную сложность алгоритма вычисления факториала целого положительного числа.

Function Factorial(x:Integer): Integer;

Var m,i: Integer;

For i:=2 To x Do m:=ro*i;

Подсчитаем общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х - 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x - 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей:

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

Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk).

For i:=l To k Do AB:=AB+A[i]*B[i];

В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных.

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

Вторая проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики - исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм?

Функции, часто встречающиеся при анализе алгоритмов:

• log n (логарифмическое время),
• n (линейное время),
• n log n ,
• n 2 (квадратичное время),
• 2 n (экспоненциальное время).

Первые четыре функции имеют невысокую скорость роста и алгоритмы, время работы которых оценивается этими функциями, можно считать быстродействующими. Скорость роста экспоненциальной функции иногда характеризуют как «взрывную». Для сравнения допустим, что имеются алгоритмы, трудоемкость которых (число операций) достаточно точно отражается этими функциями. Пусть эти алгоритмы выполняются на компьютере, работающем со скоростью 10 12 операций в секунду. При длине входа n ≤ 100000 алгоритмы, скорость работы которых оценивается первыми четырьмя функциями, получат ответ за ничтожные доли секунды. Для алгоритма с трудоемкостью 2 n время работы оценивается следующим образом:

• n = 50 ≈ 19 минут,
• n = 60 ≈ 320 часов,
• n = 70 ≈ 37 лет.

Вопрос 15=49. Последовательные, циклические и рекурсивные алгоритмы.

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

Пример. Вычислить периметр треугольника со сторонами a,b,c.13

Алгоритм разветвляющейся структуры

На практике редко удается представить решение задачи в виде алгоритма

линейной структуры. Часто в зависимости от каких-либо промежуточных

результатов вычисления осуществляются либо по одним, либо по другим

формулам, т.е. в зависимости от выполнения некоторого логического условия

вычислительный процесс осуществляется по одной или другой формуле.

Алгоритм такого вычислительного процесса называется алгоритмом

разветвляющейся структуры.

Ветвление - управляющая структура, организующая выполнение лишь

одного из двух указанных действий в зависимости от справедливости

некоторого условия.

Условие - вопрос, имеющий два варианта ответа: да или нет.

Запись ветвления выполняется в двух формах: полной и неполной (Рис. 1 а, б).

а) полная форма б) неполная форма

Циклические алгоритмы – алгоритмы, в которых приходится многократно вычислять значения по одним и тем же математическим зависимостям (блок схемам) для различных значений входящих в них величин. Использование циклов позволяет существенно сократить объем схемы

алгоритма и длину соответствующей ей программы. Различают циклы с

заданным и неизвестным числом повторений. С заданным числом повторений -

цикл со счетчиком. С неизвестным числом повторений - цикл с предусловием,

цикл с постусловием.

Функция (или процедура), которая прямо или косвенно обращается к себе, называется рекурсивной. Рекурсия - метод определения функции через её предыдущие и ранее определенные значения, а так же способ

организации вычислений, при котором функция вызывает сама себя с другим аргументом

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

решение получается достаточно легко. Далее "обратный ход" дает последовательные решения для задачи все большего размера, вплоть до первоначального. В основе реализации процедуры с рекурсией лежит стек (память "магазинного" типа), где хранятся данные, участвующие во всех вызовах процедуры, при которых она еще не завершила свою работу. Рекурсия – это способ организации процесса вычисления, когда алгоритм обращается сам к себе. Принцип рекурсии позволяет решить сложную задачу путем последовательного решения более простых подзадач.Как правило, рекурсия необходима в тех случаях, когда требуется перебрать слишком много вариантов. Рекурсию принято считать как одну из разновидностей циклического алгоритма. Рекурсивная форма организации позволяет придать алгоритму более компактный вид. Таким образом, решается проблема от сложного к простому – содержание рекурсивного алгоритма отражает более сложный объект через более простой такого же типа. Обычно рекурсивный алгоритм содержит следующие основные части:

– условие для завершения цикла;

– тело рекурсии, которое включает действия, предназначенные для

выполнения на каждой итерации;

– шаг рекурсии, на котором рекурсивный алгоритм вызывает сам себя.

Различают прямую и косвенную рекурсию. В первом случае алгоритм

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

называется косвенно рекурсивной.

Основное требование к рекурсивным алгоритмам – процесс обращения не

должен быть бесконечным. Другими словами, должна быть реализована

проверка завершения вызова, или в рекурсивном определении должно

присутствовать ограничение, при котором дальнейшая инициализация

рекурсии прекращается.

Примером рекурсивной функции является вычисление факториала числа.

int factoria(int n)

if (n) return n* factoria(n-1);

else return 1;

Пример рекурсивной процедуры:

procedure Rec(a: integer); begin if a>0 then Rec(a-1); writeln(a); end;

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.

Для оценки эффективности алгоритма наиболее важными показателями являются:

Время выполнения алгоритма,
- требуемый объем оперативной памяти.

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

Упрощения для оценки времени выполнения алгоритмов

В работах Д.Кнута был предложен следующий подход для анализа времени выполнения алгоритмов: общее время складывается из величин стоимость * частота для каждой базовой операции. В число базовых операций могут входить сложение, умножение, деление, получение элемента по индексу из массива, сравнение целых чисел и т.д. Нетрудно заметить, что в этом случае вычисление оценки времени выполнения алгоритма довольно-таки утомительно. Поэтому А.Тьюринг сказал, что удобно пользоваться даже грубыми приближениями оценок времени выполнения алгоритмов: можно присвоить веса различным операциям в зависимости от их частоты появления во время работы алгоритма и учитывать только те операции, которым соответствуют наибольшие веса. Например, при перемножении матриц следует учитывать только такие операции, как умножение и запись чисел, т.к. это самые частые операции. Рассмотрение только наиболее часто встречающихся операций - первое упрощение , предложенное для приблизительного расчета времени выполнения алгоритмов.

Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число N характеризует размер входных данных),

\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),

вместо \(1/6N^3\) пишут "этот алгоритм имеет сложность \(O(N^3)\), вместо \(3N^4\) пишут "этот алгоритм имеет сложность \(O(N^4)\)".

Определение O-большого

Говорят, что \(f\) является "O большим" от \(g\) при \(x \to x_0\), если существует такая константа \(C>0\), что для всех \(x\) из окрестности точки \(x_0\) имеет место неравенство \(|f(x)| \leq C|g(x)|\). Ниже приведена иллюстрация определения (ось \(x\) - размер входных данных, ось \(y\) - время выполнения алгоритма). Мы видим, что начиная с некоторой точки при стремлении размера входных данных к \(\propto\) \(f(n)\) растет медленнее, чем \(g(n)\) и вообще \(g(n)\) как бы ограничивает ее сверху.

Примеры. \(1 = O(N), N = O(N^2).\)

Наряду с оценками вида \(O(N)\) используется оценка \(\Omega(N)\) (омега большое). Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция \(f(N)=\Omega(N^2)\). Это значит, что даже в самом удачном случае будет произведено не менее \(N^2\) действий. В то время как оценка \(O(N^3)\) гарантирует, что в худшем случае будет не более чем порядка \(N^3\) действий. Также используется оценка \(\Theta(N)\) (тэта), которая является верхней и нижней асимптотической оценкой, когда \(O(N)\) и \(\Omega(N)\) совпадают. Итак, \(O(N)\) - приближенная оценка алгоритма на худших входных данных, \(\Omega(N)\) - на лучших входных данных, \(\Theta(N)\) - сокращенная запись одинаковых \(O(N)\) и \(\Omega(N)\).

Оценки времени выполнения для разных алгоритмов

Обозначим T(N) - время выполнения алгоритма. Пусть исследуемый алгоритм имеет вид:

1. набор инструкций, включающих только базовые операции:

Statement 1;
...
statement k;

Тогда T(N) = T(statement 1) + ... + T(statement k).

Т.к. каждая инструкция включает только базовые операции, то время выполнения этого куска кода не зависит от размера входных данных (не растет с ростом размера входных данных), т.е. является константой. Этот алгоритм имеет сложность O(1).

2. if-else инструкции

If (condition) {
sequence of statements 1
}
else {
sequence of statements 2
}

Здесь выполнится либо sequence of statements 1, либо sequence of statements 2, поэтому, т.к. мы хотим получить оценку времени выполнения в наихудшем случае, T(N) = max(T(sequence of statements 1), T(sequence of statements 2)). Например, если время выполнения sequence of statements 1 будет O(N), а sequence of statements - O(1), то T(N) = O(N).

For (i = 0; i < N; i++) {
sequence of statements
}

Т.к. цикл выполнится N раз, то sequence of statements тоже выполнится N раз. Если T(sequence of statements) = O(1), то T(N) = O(N)*O(1) = O(N).

4. Вложенные циклы.

For (i = 0; i < N; i++) {
for (j = 0; j < M; j ++){
...
}
}

Внешний цикл выполняется N раз. Каждый раз, когда выполняется внешний цикл, выполняется внутренний цикл M

Теперь рассмотрим такой код:

For (i = 0; i < N; i++) {
for (j = i + 1; j < N; j ++){
sequence of statements
}
}

Посмотрим на изменение количества итераций внутреннего цикла в зависимости от итерации внешнего цикла.

I цикл j (кол-во раз выполнения)
0 N
1 N-1
2 N-2
...
N-1 1

Тогда sequence of statements выполнится N + N-1 + ... + 1 раз. Для быстрого подсчета подобных сумм пригодятся формулы из матанализа, в данном случае формула

Т.е. этот алгоритм будет иметь сложность \(O(N^2)\).

А вот и другие наиболее часто нужные формулы, полезные для подобных случаев:

4. Когда утверждение включает вызов метода, то оценка времени выполнения утверждения рассчитывается с учетом оценки времени выполнения метода. Например:

for (j = 0; j < N; j ++){

Если время выполнения метода \(g(N)=O(N)\), то \(T(N) = O(N)*O(N) = O(N^2)\).

5. Двоичный(бинарный) поиск.

Int l = 0;
int u = A.length - 1
int m;
while (l <= u) {
m = l + (u - 1)/2
if A[m] < k {
l = m +1;
}
else if A[m] == k {
return m;
}
else{
u = m - 1;
}
}
return -1;

Двоичный поиск позволяет найти индекс числа k в отсортированном массиве, если этого числа в нем нет, то возвращается -1. Сначала мы сравниваем k с числом, находящимся в середине массива. Если k меньше этого числа, то дальше мы должны искать его в левой половине массива, если больше - то в правой половине. Далее k сравнивается с числом, находящимся в середине выбранной на предыдущем шаге половины массива и т.д. С каждой итерацией пространство поиска сужается вдвое. Возникает вопрос: сколько итераций необходимо будет проделать в наихудшем случае (т.е. когда в массиве так и не будет найдено число, равное k и не останется данных для сравнения).

Мы видим, что после 1 итерации останется \(N/2\) данных для поиска индекса \(k\), после 2 итерации останется \(N/4\) данных, после 3 итерации - \(N/8\) и т.д. Мы узнаем количество итераций в наихудшем случае, если решим уравнение \(\frac{N}{2^x}=1\). Это уравнение равносильно уравнению \(2^x=N\), отсюда \(x=log_{2}(N)\) или \(x=lg(N)\) (см. определение логарифма). Поэтому оценка сложности алгоритма бинарного поиска - \(O(logN)\).

Хорошая новость заключается в том, что для характеризации времени выполнения большинства алгоритмов достаточно всего нескольких функций: \(1, logN, N, NlogN, N^2, N^3, 2^N\). На графике проиллюстрированы различные скорости роста времени выполнения алгоритма в зависимости от размера входных данных:

Из этого графика, в частности, видно, что если время выполнения алгоритма "логарифмическое", т.е. алгоритм имеет сложность \(O(logN)\), то это очень круто, т.к. время его выполнения очень медленно растет с увеличением размера входных данных, если время выполнения линейно зависит от размера входных данных, то это тоже неплохо, а вот алгоритмы с экспоненциальным временем работы (\(O(2^N)\)) лучше не использовать совсем или использовать только на данных очень малого размера.

классы P и NP

Вещественная неотрицательная функция \(f(m)\), определенная для целых положительных значений аргумента, называется полиномиально ограниченной, если существует полином \(P(m)\) с вещественными коэффициентами такой, что \(f(m) \leq P(m)\) для всех \(m \in N^+\). Задачи, для которых существуют алгоритмы с "полиномиальным" временем работы принадлежат классу P (эти задачи в основном решаются быстро и без каких-либо проблем).

Формальное определение. Язык L принадлежит классу P, тогда и только тогда, когда существует детерминированная машина Тьюринга M, такая, что:

При любых входных данных M заканчивает свою работу за полиномиальное время,
- для всех \(x \in L\) M выдает результат 1,
- для всех \(x\), не принадлежащих \(L\), M выдает результат 0.

Задачи класса NP - задачи, удовлетворяющие условию: если имеется ответ (возможное решение), то его легко верифицировать - проверить, является оно решением или нет.

Рассмотрим пример задачи из класса NP. Пусть дано множество целых чисел, например, {-7,-3, -2, 5, 8}. Требуется узнать, есть ли среди этих чисел 3 числа, которые в сумме дают 0. В данном случае ответ "да" (например, такой тройкой являются числа {-3,-2,5}. При возрастании размера множеств целых чисел количество подмножеств, состоящих из 3 элементов, экспоненциально возрастает. Между тем, если нам дают одно такое подмножество (его еще называют сертификатом), то мы легко можем проверить, равна ли 0 сумма его элементов.

Формальное определение:

Язык L принадлежит классу NP, тогда и только тогда, когда существуют такие полиномы \(p\) и \(q\) и детерминированная машина Тьюринга M, такие, что:

Для любых \(x,y\) машина M на входных данных \((x,y)\) выполняется за время \(p(|x|)\),
- для любого \(x \in L\) существует строка \(y\) длины \(q(|x|)\), такая что \(M(x,y)=1\),
- для любого \(x\) не из \(L\) и всех строк длины \(q(|x|)\) \(M(x,y)=0\).

Полиномиальная сводимость или сводимость по Карпу. Функция \(f_1\) сводится к функции \(f_2\), если существует функция \(f \in P\), такая, что для любого \(x\) \(f_{1}(x)=f_{2}(f(x))\).

Задача T называется NP-полной , если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время. Пожалуй, наиболее известным примером NP-полной задачи является задача SAT(от слова satisfiability). Пусть дана формула, содержащая булевы переменные, операторы "И", "ИЛИ", "НЕ" и скобки. Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула приняла значение "истина ".

Задача T называется NP-трудной , если для нее существует такая NP-полная задача, которая сводится к T за полиномиальное время. Здесь имеется в виду сводимость по Куку. Сведение задачи \(R_1\) к \(R_2\) по Куку - это полиномиальный по времени алгоритм, решающий задачу \(R_1\) при условии, что функция, находящая решение задачи \(R_2\), ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.

Вот возможные соотношения между вышеупомянутыми классами задач (ученые до сих пор не уверены, совпадает ли P и NP).

Наверняка вы не раз сталкивались с обозначениями вроде O(log n) или слышали фразы типа «логарифмическая вычислительная сложность» в адрес каких-либо алгоритмов. И если вы так и не понимаете, что это значит, - эта статья для вас.

Оценка сложности

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Допустим, некоторому алгоритму нужно выполнить 4n 3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n . Тогда говорят, что временная сложность этого алгоритма равна О(n 3) , т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n) .

Примеры

O(n) - линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) - логарифмическая сложность

Простейший пример - бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива - там его точно нет. Если же меньше, то наоборот - отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n 2) - квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n , т. е. n 2 .

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

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

Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.

Глава 2. Сложность алгоритмов.

2.1 Временная и вычислительная сложность алгоритмов.

Временная сложность алгоритма (T (N ) , где N – размер задачи) – это время выполнения алгоритма, измеренное в шагах (инструкциях алгоритма, которые нужно выполнять для достижения результата). Т. е. это – число элементарных операций, из которых складывается алгоритм решения задачи (:=, <>, =, +, –, *, /; and, or, not, xor; call, return).

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

https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60">

Случай T (N )= C * N 2 применим для квадратной матрицы.

Элементарные операции в данном случае – совокупность «+» и «*».

Если исходная матрица – единичная, то получаем Best Case.

Если в матрице половина элементов – 0, половина – 1, то получаем Average Case.

Константа С , которая не может быть точно выражена, характеризует влияние внешних факторов на время выполнения алгоритмов (быстродействие ЭВМ, скорость компиляции). Поэтому использование единиц времени для оценки временной сложности алгоритмов не совсем корректно. В этом случае говорят, что временная сложность алгоритма умножения матрицы на вектор пропорциональна N 2 .

2.2 O и Ω – нотации.

Характер поведения временной сложности при увеличении N (N ® ¥ ) называется асимптотической сложностью алгоритма.

Для описания скорости роста асимптотической сложности используется О-нотация. Когда говорят, что временная сложность алгоритма имеет порядок N 2 :

T (N )= O (N 2 )= O (f (N )),

То подразумевается, что существуют положительные константы C , n0= const (C >0), такие, что для всех N ³ N 0 выполняется неравенство

T (N ) £ C * f (N )

Это – верхняя граница оценки сложности.

Пример 2 :

Пусть Т(0)=1, Т(1)=4, …, Т(N )=(N +1)­­­­2 , тогда временная сложность этого алгоритма имеет порядок роста T (N )= O (N 2 ).

Можно показать, что для всех N > n 0 при n 0 = 1, C = 4 выполняется неравенство (1).

(N +1)2 £ 4* N 2

Пример 3 :

Если временная сложность записывается в виде полинома

T (N )= C 1 N 2 + C 2 N + C 3 ,

то такой алгоритм имеет порядок сложности, кратный степени максимального элемента полинома, т. к. он растет наиболее быстро при N ® ¥ :

T (N )= O (N 2 ).

Например:

3 n 2 +5 n +1 £ 5 n 2

" n ³ 1

Пример 4 :

Если некоторый алгоритм имеет сложность, кратную 3 n , тогда можно показать, что порядок роста скорости не может быть кратен O (2 n ):

T (N )=3 n ¹ O (2 n ).

Пусть существуют константы C , n 0 , такие, что выполняются неравенство:

3­­­­­ n £ C *2 n , n > n 0 .

Отсюда получаем:

С ³ (3/2)2, n > n 0 .

Но при n ® ¥ не существует такой константы С , которая удовлетворяла бы данному неравенству.

Кроме верхней границы сложности существует и нижняя граница скорости роста временной сложности:

T (N ) ³ W (f (N ))

Неравенство (2) подразумевает, что существует некоторая константа С , для которой при N ® ¥ временная сложность

T (N ) ³ C * f (N ).

Учитывая сложность точного определения T(N) (асимптотической временной сложности), в зависимости от размеров исходных данных на практике используют нижние и верхние границы временной сложности алгоритма:

T (N ) = q (f (N ))

В зависимости от значения константы С скорость роста сложности алгоритма может существенно меняться.

Пример 5 :

Пусть временная сложность записывается формулой

T(N)=3n2 –100n+6=O(n2)

3n2 >3n2 –100n+6, n ³ 1, C=3.

Если С1 » 0 (С1=0,00001) , тогда неравенство

10-5 n 2 > 3 n 2 –100 n +6, n ³ 1

не выполняется.

Но можно показать, что порядок роста сложности

3n2 –100n+6 ¹ O(N).

C*N < 3N2, N>C.

3n2 –100n+6=(n2)

C =2.29, n ³ n 0.

2.99* n 2 < 3 n 2 –100 n +6

Можно показать, что нижняя граница

3 n 2 –100 n +6 ¹ W (n 3 ) при С=1.

Неравенство 3 n 2 –100 n +6 ³ n 3 не выполняется.

3 n 2 –100 n +6= W (n )

C 1 = , n > n 0 .

https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src=">

f 1 (N )=100 n 2

f 2 (N )=5 n 3

n 0 =20 – критическая точка.

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

0 " style="margin-left:5.4pt;border-collapse:collapse;border:none">

n !

Пример 6:

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

В этом случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для решения задач с малыми размерами данных (n ® 0 ).

Пусть заданы пять алгоритмов решения одной и той же задачи, имеющие сложности:

А1: 100 N

А2: 100 N * logN

А3: 10 N 2

А4: N 3

А5: 2 N

Тогда для задач с N =2 ¸ 9 более быстродействующим будет А5 (f (N ) ~ 4 ¸ 512 ). Другие алгоритмы при подстановке дадут существенно более низкие показатели.

При N =10 ¸ 58 предпочтительным оказывается А3.

При N =59 ¸ 1024 самым эффективным будет А2.

При N >1024 предпочтителен А1.

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

Правило сумм : Пусть программа состоит из двух последовательно выполняющихся алгоритмов Р1 и Р2, для которых определены сложности O (f (n )) и O (g (n )) соответственно. Тогда временная сложность всей программы будет определяться как сумма временных сложностей каждого из алгоритмов:

T (n ) = T 1 (n )+ T 2 (n )

В общем случае получаем:

T(n) Þ O(max f(n), g(n))

Правило произведений: Пусть временная сложность программы, состоящей из двух параллельно выполняющихся алгоритмов, имеющих порядок сложности O (f (n )) и O (g (n )) соответственно, определяется как произведение временных сложностей каждого из алгоритмов:

T (n ) = T 1 (n )* T 2 (n )

В общем случае:

T (n ) Þ O (f (n )* g (n ))

Логарифмы.

2.3. Рекурсия.

Сложность рекурсивных алгоритмов оценить непросто в силу вложенности алгоритмических структур

f (n ) Þ f (n * f (n -1))

Например, для рекурсивного вычисления алгоритма n! Сложность будет зависеть от сложности каждого из алгоритмов, входящих в рекурсию.

В общем случае T (n ) ~ O (N ).

Другие рекурсивные алгоритмы в общем случае имеют временную сложность T (n ) ~ O (an ) , где a = const , что в результате дает суммарную сложность, большую, чем сложность не рекурсивного алгоритма решения этой же задачи.

2.4 Оценка сложности алгоритмов и программ.

2.4.2 Алгоритмы восстановления зависимостей.

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

Для построения аналитической зависимости сложности программы оценивают функцию T (N ) на некотором интервале [ Nmin , Nmax ] . Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации.

Как правило, в качестве такой функции используют известные функции временной сложности: O (n !), O (XN ), O (NX ), O (logN ), O (https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">В результате эксперимента над программой была получена таблица временных сложностей:

В результате поиска аппроксимации функции была получена следующая аналитическая зависимость:

https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src=">

Пример 2:

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

В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.

Трудоемкость" href="/text/category/trudoemkostmz/" rel="bookmark">трудоемкостью (временем работы).

Полиномиальный или экспоненциальный характер работы алгоритма инвариантен относительно формы представления входных данных (двоичная, десятичная или другая система счисления).

Говорят, что алгоритм является полиномиальным, если время его работы, т. е. временная сложность, ограничивается сверху полиномом некоторой степени T (N )= O (Nm ) . Тогда все задачи, которые решаются таким алгоритмом, образуют Р-класс задач. Говорят, что эти задачи входят в Р.

Задачи, временная сложность которых экспоненциальна (T (N )= O (K N ) ), не входят в Р.

Замечание : Можно показать, что задачи с линейной сложностью входят в Р

T (N )= O (N 1 )

Введем класс NP-задач, которые можно решить за полиномиальное время с помощью недетерминированного алгоритма.

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

В недетерминированном алгоритме (НДА) для любого данного состояния может быть больше одного допустимого следующего состояния, т. е. такой алгоритм в каждый момент времени может выполнить больше одного оператора.

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

Пример :

Детерминированный алгоритм (ДА) решал бы эту задачу последовательно (перебор всех вариантов, сравнение с критерием оптимальности K0 до тех пор, пока не выберет альтернативу А0).

НДА может одновременно (параллельно) получить все альтернативы и сравнить с K0, копируя самого себя в виде отдельного процесса для каждой альтернативы, которая выполняется независимо.

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

Т. о. НДА характеризуется тремя параметрами:

1. выбор – многозначная функция, значения которой являются элементами множества S;

2. неудача заставляет копию алгоритма прекратить работу;

3. успех заставляет все копии алгоритма прекратить работу и сформировать результат.

Очевидно, что никакое физическое устройство не способно на неограниченное недетерминированное поведение, значит, НДА является теоретическим методом.

Задачи, которые можно решить с помощью полиномиального НДА, образуют класс NP-задач.

2.5.2 NP -трудные и NP -полные задачи.

Задача, входящая в Р, является NP -трудной , если существует полиномиальный ДА (ПДА) ее решения, который модно использовать для получения решения всех задач, входящих в NP. Т. е. такая задача является NP-трудной, если она, по крайней мере, так же трудна, как любая задача, входящая в NP.

NP-трудная задача, принадлежащая NP, называется NP -полной задачей. Такие задачи не менее трудны, чем любая задача из NP. При этом существование ПДА для NP-трудной или NP-полной задачи означает, что классы Р и NP совпадают, т. е. возможно решение всех задач 3-го класса быстрым алгоритмом.

Для доказательства того, что задача является NP-трудной, необходимо показать, что если для задачи существует ПДА, то его можно использовать для получения другого ПДА решения задач, входящих в NP.

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

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

Определение 1 : Задача Р1 преобразуется в задачу Р2, если любой частный случай задачи Р1 можно преобразовать за полиномиальное время в некоторый частный случай задачи Р2. Тогда решение Р1 можно получить за полиномиальное время из решения частного случая задачи Р2.

https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56">

Например:

f 2 (xi )=(x 1 Ú x 2 ) Ù ( ) Ù ()

не является выполнимой, т. к. при любых xi f 2 (xi )= false .

Теорема :

Задача о выполнимости является NP-полной.

xi выбор (true, false)

if E(x1, x2, …, xN) then успех

else неудача

Используя преобразование задачи Р1 в Р2, можно показать, что даже ограниченный случай задачи о выполнимости является NP-полным.

К-выполнимость .

К-выполнимость означает, что любой дизъюнкт, входящий в КНФ, содержит не более К логических переменных.

Минимальный случай К=3. Для булевской функции, представленной в КНФ, за полиномиальное время можно найти функцию Е*(х2) , содержащую не более трех переменных в каждом дизъюнкте. Тогда Е выполнима, если выполнима Е*.

E * (x 1 , x 2 ,…, xn ) ® E * (xi )

Для этого используется метод уменьшения порядка дизъюнкта

(a 1 Ú a 2 Ú … Ú a k )=(a 1 Ú a 2 Ú z ) Ù (a 3 Ú a 4 Ú … Ú a k Ú )

Применяя итерационный процесс разложения, можно получить Е* .

Найти алгоритм решения Е* проще, чем функции Е . Но при этом доказав выполнимость Е* , докажем выполнимость исходной функции Е .

Частный случай: при К=2 функция Е входит в Р.

Примерами задач NP-класса могут послужить также задачи на графах :

1) Определение максимума клик неориентированного графа (NP-трудная задача).

2) Задача определения полного подграфа (NP-полная задача).

3) Определение вершинного покрытия мощности L для неориентированного графа (NP-полная задача).

4) Определение максимума вершинных покрытий неориентированного графа (NP-трудная задача).

5) Задача определения существования Гамильтонова цикла для графа (NP-полная задача).

6) Задача коммивояжера: определение оптимального движения по графу с единым вхождением в каждую вершину (NP-трудная задача).

7) Задача составления расписания (NP-полная задача).

2.6 Алгоритмически неразрешимые проблемы

Разделяют проблемы одиночные и массовые .

Например:

5+7=? – одиночная проблема.

х+у=? – массовая проблема.

Принципиально неразрешимыми должны быть алгоритмы получения объектов, которые парадоксальны, или решения задач, из которых вытекало бы существование парадоксальных объектов.

Например, парадоксами являются:

Пример 1:

10-ая проблема Гильберта.

Д. Гильберт в 1901 г. при решении диофантовых уравнений выдвинул проблему, которая гласит:

Найти алгоритм, определяющий некоторое целочисленное решение для произвольного диофантового уравнения

F (x , y , …)=0

Это – полином с целыми показателями степеней и целыми коэффициентами при неизвестных

anxn+an-1xn-1+…+a2x2+a1x+a0=0

Для приведенного уравнения существует частное решение, которое заключается в том, что всякий целочисленный корень xi является делителем a 0 . При этом a 0 раскладывают на простые множители и проверяют каждый множитель на соответствие корню.

В 1970 г. ленинградский математик Ю. Матиясевич математически доказал алгоритмическую невозможность решения диофантового уравнения в общем виде.

Пример 2:

Теорема Ферма:

Не существует таких целых чисел a , b , с, n (n >2) , для которых справедливо равенство

an + bn = cn

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

Пример 3:

Проблема Гольдбаха.

Х. Гольбах в 1742 г. в письме к Эйлеру сформулировал проблему:

Доказать, что каждое целое число N ³ 6 может быть представлено в виде суммы трех простых чисел

N = a + b + c

Это значит, что нужно найти алгоритм, который позволил бы для любого целого числа N ³ 6 найти хотя бы одно разложение на три простых слагаемых.

Частый случай решения этой проблемы предложил Эйлер: для четных N эта проблема разрешима и равносильна разложению на два простых слагаемых.

И. Виноградов в 1937 г. доказал, что для нечетных N можно найти три простых слагаемых, но для четных чисел решение не найдено до сих пор.

Обозначение	Интуитивное объяснение	Определение
	f ограничена сверху функцией g	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> или style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	f ограничена снизу и сверху функцией g асимптотически	0), n_0: \forall (n>n_0) \; |Cg(n)|
	g доминирует над f асимптотически	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	f доминирует над g асимптотически	style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	f эквивалентна g асимптотически

Примеры

Замечания

Необходимо подчеркнуть, что степень роста наихудшего времени выполнения - не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения:

Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n C , а при другом - порядка n+n!/C, где C - постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй - нет, хотя, например, при С=10 (10 10) дело обстоит как раз наоборот.

1. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но «хитрые» алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.
2. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество «эффективности» алгоритма.
3. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

Классы сложности

Класс сложности - это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

Класс P

Проблема равенства классов P и NP

Знаменитые ученые

• Леонид Левин
• Александр Разборов
• Эди Шеймир

См. также

Ссылки

• Юрий Лифшиц «Современные задачи теоретической информатики » . Курс лекций по алгоритмам для NP-трудных задач.
• А. А. Разборов Theoretical Computer Science: взгляд математика // Компьютерра . - 2001. - № 2. (альтернативная ссылка)
• А. А. Разборов О сложности вычислений // Математическое просвещение . - МЦНМО , 1999. - № 3. - С. 127-141.

Wikimedia Foundation . 2010 .

Смотреть что такое "Временная сложность алгоритма" в других словарях:

временная сложность (алгоритма) - — Тематики защита информации EN time complexity … Справочник технического переводчика

СЛОЖНОСТЬ ОПЕРАТОРСКОЙ ДЕЯТЕЛЬНОСТИ - совокупность объективных факторов, влияющих на качество и продолжительность выполнения человеком требуемых функций в СЧМ. С. о. д. разделяется на несколько видов, каждый из которых характеризуется совокупностью факторов, определенным образом… … Энциклопедический словарь по психологии и педагогике

Вычислений функция, дающая числовую оценку трудности (громоздкости) процессов применения алгоритма к исходным данным. Уточнением А. с. вычислений служит понятие сигнализирующей функции (или просто сигнализирующей) функции, к рая задается… … Математическая энциклопедия

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

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

Это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия

Алгоритм сортировки это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в… … Википедия

- (GM) криптографическая система с открытым ключом, разработанная Шафи Голдвассером и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических… … Википедия Подробнее