Для оценки эффективности алгоритма наиболее важными показателями являются:
- время выполнения алгоритма,
- требуемый объем оперативной памяти.
В наши дни, в силу полувека технического прогресса, первый показатель (время выполнения) зачастую значительно важнее, чем второй, поэтому далее подробно остановимся только на нем.
Примеры. \(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)\).
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).
3. Циклы.
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<N раз. Если мы хотим получить оценку времени выполнения в наихудшем случае, то \(T(N)=O(M*N)=O(N^2)\), если \(M<N\).
Теперь рассмотрим такой код:
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)\).
А вот и другие наиболее часто нужные формулы, полезные для подобных случаев:
Если время выполнения метода \(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\). На графике проиллюстрированы различные скорости роста времени выполнения алгоритма в зависимости от размера входных данных:
Вещественная неотрицательная функция \(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\).
Задача T называется NP-полной, если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время. Пожалуй, наиболее известным примером NP-полной задачи является задача SAT(от слова satisfiability). Пусть дана формула, содержащая булевы переменные, операторы "И", "ИЛИ", "НЕ" и скобки. Задача заключается в следующем: можно ли назначить всем переменным, встречающимся в формуле, значения ложь и истина так, чтобы формула приняла значение "истина".
Задача T называется NP-трудной, если для нее существует такая NP-полная задача, которая сводится к T за полиномиальное время. Здесь имеется в виду сводимость по Куку. Сведение задачи \(R_1\) к \(R_2\) по Куку - это полиномиальный по времени алгоритм, решающий задачу \(R_1\) при условии, что функция, находящая решение задачи \(R_2\), ему дана в качестве оракула, то есть обращение к ней занимает всего один шаг.
Вот возможные соотношения между вышеупомянутыми классами задач (ученые до сих пор не уверены, совпадает ли P и NP):
Вот еще 2 примера NP-полных задач.
Задача о рюкзаке. Даны объемы \(w_1, ..., w_n \in N\) и стоимости \(v_1, ..., v_n \in N\) набора из \(N\) предметов. Также даны общий объем \(W\) и число \(g\). Необходимо найти множество предметов из набора, общий объем которых не превышает \(W\), а общая стоимость не превышает \(g\).
Задача о коммивояжере. Дано \(n\) вершин с номерами \(1,...,n\) и все \(n(n-1)/2\) попарных расстояний между ними, а также число \(b\). Найти цикл, проходящий через все вершины ровно по одному разу и имеющий длину не более \(b\), или же сообщить, что такого цикла нет. Другими словами, необходимо найти перестановку \(\tau(1), ..., \tau(n)\) вершин такую, что \(d_{\tau(1)} + ... + d_{\tau(n)} \leq b \).
Для нахождения решений NP-трудных задач в худшем случае требуется осуществить полный перебор всех вариантов, при этом часто нужно генерировать все возможные перестановки и проверять их на удовлетворение некоторого свойства.
Время выполнения задач, решение которых связано с перестановками, быстро выходит из-под контроля потому, что число всех возможных перестановок сильно растет с возрастанием количества элементов перестановки. Например, для множества из 5 элементов можно сгенерировать 5!=5*4*3*2*1=120 перестановок, а для множества из 6 элементов перестановок сгенерируется уже в 6 раз больше, и т.д.
Во многих случаях для решения таких задач используются эвристические подходы, которые гарантируют не оптимальное, но рациональное решение.
Информационные источники:
O большое и o малое (википедия), Complexity and Big-O notations notes, Algorithmic Complexity, Об использовании символов o и O, Логарифм (википедия), Coursera course on Algorithms and Data structures, Part1 (презентация), Algolist. Оценки времени выполнения, форум RSDN, Алгоритмы для NP-трудных задач (презентация), P_(complexity) (wikipedia), NP_(complexity) (wikipedia), Полиномиальная сводимость, Задача выполнимости булевых формул (википедия), Сведение по Куку (википедия), Доклад "Переборные задачи", форум ixbt, Абрамов. Лекции о сложности алгоритмов
- время выполнения алгоритма,
- требуемый объем оперативной памяти.
В наши дни, в силу полувека технического прогресса, первый показатель (время выполнения) зачастую значительно важнее, чем второй, поэтому далее подробно остановимся только на нем.
Упрощения для оценки времени выполнения алгоритмов
Говорят, что \(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)\) как бы ограничивает ее сверху.
В работах Д.Кнута был предложен следующий подход для анализа времени выполнения алгоритмов: общее время складывается из величин стоимость * частота для каждой базовой операции. В число базовых операций могут входить сложение, умножение, деление, получение элемента по индексу из массива, сравнение целых чисел и т.д. Нетрудно заметить, что в этом случае вычисление оценки времени выполнения алгоритма довольно-таки утомительно. Поэтому А.Тьюринг сказал, что удобно пользоваться даже грубыми приближениями оценок времени выполнения алгоритмов: можно присвоить веса различным операциям в зависимости от их частоты появления во время работы алгоритма и учитывать только те операции, которым соответствуют наибольшие веса. Например, при перемножении матриц следует учитывать только такие операции, как умножение и запись чисел, т.к. это самые частые операции. Рассмотрение только наиболее часто встречающихся операций - первое упрощение, предложенное для приблизительного расчета времени выполнения алгоритмов.
Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число N характеризует размер входных данных),
\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),
\(3N^4 - N^2 + 12N \sim 3N^4\).
Далее используют О-нотацию:
вместо \(1/6N^3\) пишут "этот алгоритм имеет сложность \(O(N^3)\), вместо \(3N^4\) пишут "этот алгоритм имеет сложность \(O(N^4)\)".
Определение O-большого
Примеры. \(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) - время выполнения алгоритма. Пусть исследуемый алгоритм имеет вид:
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).
3. Циклы.
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<N раз. Если мы хотим получить оценку времени выполнения в наихудшем случае, то \(T(N)=O(M*N)=O(N^2)\), если \(M<N\).
Теперь рассмотрим такой код:
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);
}
Если время выполнения метода \(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
Формальное определение. Язык 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):
Вот еще 2 примера NP-полных задач.
Задача о рюкзаке. Даны объемы \(w_1, ..., w_n \in N\) и стоимости \(v_1, ..., v_n \in N\) набора из \(N\) предметов. Также даны общий объем \(W\) и число \(g\). Необходимо найти множество предметов из набора, общий объем которых не превышает \(W\), а общая стоимость не превышает \(g\).
Задача о коммивояжере. Дано \(n\) вершин с номерами \(1,...,n\) и все \(n(n-1)/2\) попарных расстояний между ними, а также число \(b\). Найти цикл, проходящий через все вершины ровно по одному разу и имеющий длину не более \(b\), или же сообщить, что такого цикла нет. Другими словами, необходимо найти перестановку \(\tau(1), ..., \tau(n)\) вершин такую, что \(d_{\tau(1)} + ... + d_{\tau(n)} \leq b \).
Для нахождения решений NP-трудных задач в худшем случае требуется осуществить полный перебор всех вариантов, при этом часто нужно генерировать все возможные перестановки и проверять их на удовлетворение некоторого свойства.
Время выполнения задач, решение которых связано с перестановками, быстро выходит из-под контроля потому, что число всех возможных перестановок сильно растет с возрастанием количества элементов перестановки. Например, для множества из 5 элементов можно сгенерировать 5!=5*4*3*2*1=120 перестановок, а для множества из 6 элементов перестановок сгенерируется уже в 6 раз больше, и т.д.
Во многих случаях для решения таких задач используются эвристические подходы, которые гарантируют не оптимальное, но рациональное решение.
Информационные источники:
O большое и o малое (википедия), Complexity and Big-O notations notes, Algorithmic Complexity, Об использовании символов o и O, Логарифм (википедия), Coursera course on Algorithms and Data structures, Part1 (презентация), Algolist. Оценки времени выполнения, форум RSDN, Алгоритмы для NP-трудных задач (презентация), P_(complexity) (wikipedia), NP_(complexity) (wikipedia), Полиномиальная сводимость, Задача выполнимости булевых формул (википедия), Сведение по Куку (википедия), Доклад "Переборные задачи", форум ixbt, Абрамов. Лекции о сложности алгоритмов
Комментариев нет:
Отправить комментарий