Анализ алгоритмов | Big-O analysis

В наших предыдущих статьях об анализе алгоритмов мы вкратце обсудили асимптотические обозначения, их наихудшую и наилучшую производительность и т.д. В этой статье мы подробно рассмотрим анализ алгоритма с использованием асимптотической нотации Big – O. Big-O анализ алгоритмов

Мы можем выразить сложность алгоритма, используя нотацию Big-O. Для задачи размера N:

• Функция/метод постоянного времени имеет “порядок 1” : O(1)
• Функция/метод линейного времени имеет “порядок N” : O(N)
• Функция/метод квадратичного времени имеет “порядок N в квадрате” : O(N 2 )

Definition: Let g and f be functions from the set of natural numbers to itself. The function f is said to be O(g) (read big-oh of g), if there is a constant c > 0 и натуральное число n₀ такое, что f(n) ≤ cg(n) для всех n ≥ n.₀ .

Примечание: O(g) – это множество!

Злоупотребление обозначениями: f = O(g) не означает, что f ∈ O(g). Асимптотическая нотация Big-O дает нам идею верхней границы, математически описанную ниже:

f(n) = O(g(n)), если существует целое положительное число n₀ и положительная постоянная c, такая, что f(n)≤c.g(n) ∀ n≥n.₀

Общая пошаговая процедура анализа времени работы Big-O выглядит следующим образом:

1. Выясните, что такое входные данные и что представляет собой n.
2. Выразить максимальное количество операций, выполняемых алгоритмом, в терминах n.
3. Исключите все члены высшего порядка.
4. Удалите все постоянные коэффициенты.

Некоторые из полезных свойств анализа в нотации Big-O следующие:

▪ Постоянное умножение: Если f(n) = c.g(n), то O(f(n)) = O(g(n)) ; где c – ненулевая константа. ▪ Полиномиальная функция: Если f(n) = a₀ + a₁.n + a₂.n 2 + — + a_m.n m , то O(f(n)) = O(n m ). ▪ Функция суммирования: Если f(n) = f₁(n) + f₂(n) + — + f_m(n) и f_i(n)≤f_i+1(n) ∀ i=1, 2, –, m, то O(f(n)) = O(max(f₁(n), f₂(n), –, f_m(n))). ▪ Логарифмическая функция: Если f(n) = log_an и g(n)=log_bn, то O(f(n))=O(g(n)); все логарифмические функции растут одинаково в терминах Big-O.

В основном, эта асимптотическая нотация используется для теоретического измерения и сравнения наихудших сценариев алгоритмов. Для любого алгоритма анализ Big-O должен быть простым, если мы правильно определим операции, которые зависят от n, размера входа. Анализ алгоритмов во время выполнения

В общем случае для анализа производительности алгоритмов мы в основном использовали измерение и сравнение теоретического времени работы алгоритмов в наихудшем случае. Самое быстрое возможное время работы для любого алгоритма – O(1), обычно называемое постоянным временем работы. В этом случае алгоритму всегда требуется одинаковое количество времени для выполнения, независимо от размера входных данных. Это идеальное время работы алгоритма, но оно редко достижимо. В реальных случаях производительность (Runtime) алгоритма зависит от n, то есть размера входа или количества операций, необходимых для каждого элемента входа. Алгоритмы можно классифицировать следующим образом от лучшей к худшей производительности (Running Time Complexity):

▪ Логарифмический алгоритм – O(logn) Время выполнения растет логарифмически пропорционально n. ▪ Линейный алгоритм – O(n) Время выполнения растет прямо пропорционально n. ▪ Суперлинейный алгоритм – O(nlogn) Время выполнения растет пропорционально n. ▪ Полиномиальный алгоритм – O(n c ) Время выполнения растет быстрее, чем предыдущие, в зависимости от n. ▪ Экспоненциальный алгоритм – O(c n ) Время выполнения растет еще быстрее, чем полиномиальный алгоритм, исходя из n. ▪ Факториальный алгоритм – O(n!) Время выполнения растет быстрее всего и быстро становится непригодным для использования даже при малых значениях n.

Где, n – размер входа, а c – положительная константа.

Алгоритмические примеры анализа времени выполнения: Ниже приведены некоторые примеры всех этих типов алгоритмов (в худшем случае):

▪ Логарифмический алгоритм – O(logn) – Бинарный поиск. ▪ Линейный алгоритм – O(n) – Линейный поиск. ▪ Суперлинейный алгоритм – O(nlogn) – сортировка кучи, сортировка слиянием. ▪ Полиномиальный алгоритм – O(n^c) – умножение матрицы Штрассена, пузырьковая сортировка, сортировка выбором, сортировка вставками, сортировка ведрами. ▪ Экспоненциальный алгоритм – O(c^n) – Ханойская башня. ▪ Факториальный алгоритм – O(n!) – Расширение детерминанта по минорам, алгоритм перебора для задачи о коммивояжере.

Математические примеры анализа времени выполнения: Производительность (время выполнения) алгоритмов разного порядка быстро меняется по мере увеличения n (размера входных данных). Рассмотрим математический пример:

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

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

• Во-первых, за использование памяти отвечает реализация программы. Например, можно предположить, что рекурсивная реализация всегда резервирует больше памяти, чем соответствующая итеративная реализация конкретной задачи.
• И второе – n, размер входа или объем памяти, требуемый для каждого элемента. Например, простой алгоритм с большим размером входа может потреблять больше памяти, чем сложный алгоритм с меньшим размером входа.

Примеры алгоритмов для анализа “следа памяти”: Ниже приведены алгоритмы с примерами, классифицированные от лучшей к худшей производительности (Space Complexity) на основе наихудших сценариев:

Классы алгоритмов и время их выполнения на компьютере, выполняющем 1 миллион операций в секунду (1 сек = 10 6 мксек = 10 3 мсек):