Alex tools
Алгоритмическая сложность
Процесс абстрагирования от деталей и определения скорости использования ресурсов с точки зрения размера ввода является одной из фундаментальных идей в информатике.
Асимптотические обозначения
Целью вычислительной сложности является классификация алгоритмов в соответствии с их производительностью. Мы представим функцию времени T(n), используя нотацию «big-O» для выражения сложности времени выполнения алгоритма. Например, следующее утверждение
говорит, что алгоритм имеет квадратичную сложность по времени.
Определение «big O»
Для любых монотонных функций f(n) и g(n) от целых положительных чисел до целых положительных чисел говорят, что f(n) = O(g(n)), когда существуют такие константы c > 0 и n0 > 0, так что
Интуитивно это означает, что функция f(n) не растет быстрее, чем g(n), или что функция g(n) является верхней границей для f(n) для всех достаточно больших n → ∞
Вот графическое представление отношения f(n) = O(g(n)):
«big-O» нотация не симметрична: n = O(n2) но n2 ≠ O(n).
Постоянное время: O(1)
Говорят, что алгоритм работает за постоянное время, если ему требуется одинаковое количество времени независимо от размера ввода. Примеры:
Линейное время: O(n)
Говорят, что алгоритм работает за линейное время, если его выполнение по времени прямо пропорционально размеру ввода, то есть время увеличивается линейно с увеличением размера ввода. Примеры:
Логарифмическое время: O(log n)
Говорят, что алгоритм работает за логарифмическое время, если его время выполнения пропорционально логарифму размера ввода. Пример:
Обратите внимание, log(n)
Определение понятия «big Theta»
Чтобы измерить сложность конкретного алгоритма, нужно найти верхнюю и нижнюю границы. В этом случае используется новая запись. Мы говорим, что f(n) = Θ(g(n)) тогда и только тогда, когда f(n) = O(g(n)) и f(n) = Ω(g(n)). Примеры:
Анализ алгоритмов
Термин «анализ алгоритмов» используется для описания подходов к изучению производительности алгоритмов. Существуют следующие виды анализа:
Пример. Рассмотрим алгоритм последовательного поиска в массиве размером n.
Амортизированная временная сложность
Рассмотрим стек динамических массивов. В этой модели push() удвоит размер массива, если места недостаточно. Поскольку копирование массивов не может быть выполнено в постоянное время, мы говорим, что push также не может быть сделан за постоянное время. В этом разделе мы покажем, что push() занимает амортизированное постоянное время.
Давайте посчитаем количество операций копирования, необходимых для выполнения последовательности push’ей.
Мы видим, что 3 push требуют 2 + 1 = 3 копирований.
Мы видим, что для 5 push требуется 4 + 2 + 1 = 7 копирований.
Мы видим, что для 9 push требуется 8 + 4 + 2 + 1 = 15 копирований.
Асимптотически количество копирований примерно равно количеству push.
В данном случае говорят, что алгоритм работает с амортизированным постоянным временем.
