воскресенье, 5 мая 2013 г.

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

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

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

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

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


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

Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число 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-большого

Говорят, что \(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).

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

Вещественная неотрицательная функция \(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):




Вот еще 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 notesAlgorithmic ComplexityОб использовании символов o и OЛогарифм (википедия)Coursera course on Algorithms and Data structures, Part1 (презентация)Algolist. Оценки времени выполненияфорум RSDNАлгоритмы для NP-трудных задач (презентация)P_(complexity) (wikipedia)NP_(complexity) (wikipedia)Полиномиальная сводимостьЗадача выполнимости булевых формул (википедия)Сведение по Куку (википедия)Доклад "Переборные задачи"форум ixbtАбрамов. Лекции о сложности алгоритмов

Комментариев нет:

Отправить комментарий