1. Основные понятия алгоритмизации и программирования

4. Результат работы программы: Введите элементы массива 1 2 3 4 -2 0 -3 -1 1 1 1 0 B 1-й строке 4 положительных элементов B 2-й строке 0 положительных элементов B 3-й строке 3 положительных элементов Среднее арифметическое: 0.58

9. Алгоритмы решения задач внутренней сортировки и алгоритмы поиска информации

9.1. Сложность алгоритмов

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