Асимптотическая сложность алгоритма
Асимптотическая сложность алгоритма — способ оценки вычислительной сложности алгоритма «с точностью до константы», применяемый в теории сложности. Обычно записывается в нотации «большого О».
Широко применяется, так как точная оценка сложности в элементарных операциях часто сложна (в том числе зависит и от того, что принять за элементарную операцию — одно действие в конкретном языке программирования, процессорный такт), а также не имеет смысла при больших объемах входных данных, когда медленнорастущие части временной функции практически перестают влиять на общий объем исполняемой работы.
Чаще всего используется асимптотическая оценка времени работы алгоритма сверху, записываемая как O(f(n)), где n — объем входных данных. Если принять функцию времени работы алгоритма в зависимости от объема входных данных как F(n), то можно сказать, что начиная с определенного числа N для всех n > N выполняется неравенство |F(n)| <= |N*f(n)|, иными словами, с некоторого момента функция F(n) растет не быстрее, чем N*f(n), где N — константа.
Оценки сложности алгоритмов:
- Логарифмическая сложность — зависит от входных данных n как N*log(n), в частности, таковую сложность имеет операция поиска в индексированном массиве, быстрого возведения в произвольную степень. На практике чаще встречается сложность N*n*log(n).
- Полиномиальная сложность — зависит от входных данных n как N*n^c, где c — некая конкретная степень. Указывается только старшая степень полинома, так как с ростом n меньшие степени перестают существенно влиять. Например, двойной перебор массива имеет сложность O(n²), реализация метода Шульце для n кандидатов — O(n³).
- Экспоненциальная сложность — зависит от входных данных n как N*e^n. Использования алгоритмов с такой сложностью стараются избегать, это сложные задачи на графах, сложные операции поиска по нескольким таблицам в MySQL и т. д.
Возможны и более высокие сложности, например N*n!.
