Сложность алгоритмов
Алгоритмы решения задач внутренней сортировки и алгоритмы поиска информации
Теория сложности обеспечивает методологию анализа вычислительной сложностиразличных криптографических методов и алгоритмов.
Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом, и выдающая результат вычислений на выход [4].
Чаще всего, говоря о сложности, имеют в виду временную сложность алгоритма: Т. Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Под элементарными шагами понимают такие базисные операции, как сложение, умножение, замены, безусловные передачи управления и вызовы подпрограмм.Т обычно представляется в виде функции от п,где п - это размер входных данных. Функция времени вычислений – TA (n).
Обычно вычислительная сложность алгоритма выражается с помощью нотации "О большого", т.е описывается порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4п2+7п+2, то вычислительная сложность порядка n 2, записываемая как О(п2) [4].
Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т = О(п), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т = О(2п), то добавление одного бита к входным данным удвоит время выполнения алгоритма.
Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным,если его сложность не зависит от п: О(1). Алгоритм является линейным,если его временная сложность О(п). Алгоритмы могут быть квадратичными, кубическимии т.д. Все эти алгоритмы - полиномиальные,их сложность - О(пm), где m - константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем.
Алгоритмы, сложность которых равна O(tf(n)),где t - константа, большая, чем 1, a f(n) - некоторая полиномиальная функция от n, называются экспоненциальными.Подмножество экспоненциальных алгоритмов, сложность которых равна О(с f(n)), где где с - константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.Алгоритмы, сложность которых равна O (n!), называются алгоритмами с факториальной сложностью. Таким образом, справедливо следующее соотношение:
O (log n) < O (n) < O (n log n) < O (n2) < O (n3) < O (2 n) < O (n!).
В настоящее время алгоритм считается практически полезным только в том случае, если его временная функция растет полиномиально относительно размеров входных данных, причем ограниченной степени. Практичными являются алгоритмы сложности - O (n), O (n2). Не практичны экспоненциальные и факториальные алгоритмы. Их сложность превосходит любую полиномиальную оценку.