Алгоритмическая сложность

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

Рассмотрим два классических примера: сложение двух целых чисел. Мы добавим два целых числа цифра за цифрой (или бит за битом), и это определит "шаг" в нашей вычислительной модели. Поэтому мы говорим, что сложение двух n-битных целых чисел занимает n шагов. Следовательно, общее время вычислений равно T(n) = c * n, где c - время, необходимое для сложения двух битов. На разных компьютерах добавление двух битов может занять разное время, скажем, c1 и c2, таким образом, добавление двух n-битных целых принимает T(n) = c1 * n и T(n) = c2 * n соответственно. Это показывает, что разные машины приводят к разным наклонам, но время T(n) растет линейно с увеличением входного размера.

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

Асимптотические обозначения

Целью вычислительной сложности является классификация алгоритмов в соответствии с их производительностью. Мы представим функцию времени T(n), используя нотацию "big-O" для выражения сложности времени выполнения алгоритма. Например, следующее утверждение

T(n) = O(n*n)

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

Определение "big O"

Для любых монотонных функций f(n) и g(n) от целых положительных чисел до целых положительных чисел говорят, что f(n) = O(g(n)), когда существуют такие константы c > 0 и n0 > 0, так что

f(n) ≤ c * g(n), для всех n ≥ n0

Интуитивно это означает, что функция f(n) не растет быстрее, чем g(n), или что функция g(n) является верхней границей для f(n) для всех достаточно больших n → ∞

Вот графическое представление отношения f(n) = O(g(n)):

Примеры:

1 = O(n)
n = O(n*n)
log(n) = O(n)
2n + 1 = O(n)

"big-O" нотация не симметрична: n = O(n2) но n2 ≠ O(n).

Постоянное время: O(1)

Говорят, что алгоритм работает за постоянное время, если ему требуется одинаковое количество времени независимо от размера ввода. Примеры:

• массив: доступ к любому элементу
• стек фиксированного размера: методы push и pop
• очередь фиксированного размера: методы enqueue и dequeue

Линейное время: O(n)

Говорят, что алгоритм работает за линейное время, если его выполнение по времени прямо пропорционально размеру ввода, то есть время увеличивается линейно с увеличением размера ввода. Примеры:

• массив: линейный поиск, обход, нахождение минимума
• ArrayList: метод contains
• очередь: метод contains

Логарифмическое время: O(log n)

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

• бинарный поиск

Вспомним игру "двадцать вопросов" - задача состоит в том, чтобы угадать значение скрытого числа в интервале. Каждый раз, когда вы делаете предположение, вам говорят, является ли ваше предположение слишком высоким или слишком низким. В игре "двадцать вопросов" используется стратегия, которая использует ваше число догадок, чтобы уменьшить размер интервала вдвое. Это пример общего метода решения проблем, известного как бинарный поиск:

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

Обратите внимание, log(n) < n, когда n → ∞. Алгоритмы, которые запускаются в O(log n), не используют весь ввод.

Квадратичное время: O(n*n)

Говорят, что алгоритм работает за квадратичное время, если его время выполнения пропорционально квадрату размера ввода. Примеры:

• сортировка по пузырькам, сортировка по выделению, сортировка по вставке

Определение понятия "big Omega"

Нам нужны обозначения для нижней границы. В этом случае используется заглавная omega Ω нотация. Мы говорим, что f(n) = Ω(g(n)), когда существует постоянная c, для которой f(n) ≥ c * g(n) для всех достаточно больших n. Примеры:

n = Ω(1)
n*n = Ω(n)
n*n = Ω(n log(n))
2*n + 1 = O(n)

Определение понятия "big Theta"

Чтобы измерить сложность конкретного алгоритма, нужно найти верхнюю и нижнюю границы. В этом случае используется новая запись. Мы говорим, что f(n) = Θ(g(n)) тогда и только тогда, когда f(n) = O(g(n)) и f(n) = Ω(g(n)). Примеры:

2*n = Θ(n)
n*n + 2*n + 1 = Θ(n*n)

Анализ алгоритмов

Термин "анализ алгоритмов" используется для описания подходов к изучению производительности алгоритмов. Существуют следующие виды анализа:

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

Пример. Рассмотрим алгоритм последовательного поиска в массиве размером n.

• Его наихудшая сложность во время выполнения - O(n)
• Его наилучшая сложность во время выполнения - O(1)
• Его средняя сложность во время выполнения составляет O(n/2)=O(n)

Амортизированная временная сложность

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

Давайте посчитаем количество операций копирования, необходимых для выполнения последовательности push'ей.

Мы видим, что 3 push требуют 2 + 1 = 3 копирований.

Мы видим, что для 5 push требуется 4 + 2 + 1 = 7 копирований.

Мы видим, что для 9 push требуется 8 + 4 + 2 + 1 = 15 копирований.

Как правило, для 2n + 1 push требуется 2n + 2n-1 + ... + 2 + 1 = 2n + 1 - 1 копирований.

Асимптотически количество копирований примерно равно количеству push.

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