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²). Не практичны экспоненциальные и факториальные алгоритмы. Их сложность превосходит любую полиномиальную оценку.

9.2. Постановка задачи поиска

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

Пусть задан массив, состоящий из одного или нескольких элементов любого типа, отличного от файлового. Предположим, что в некотором массиве хранится множество из n (n × m) элементов и необходимо определить положение некоторого элемента в этом массиве. Каждый элемент массива имеет индекс (индексы), причем индексы различны и однозначно идентифицируют элементы массива.

Задача поиска в этом случае состоит в отыскании индекса (индексов) элемента по заданному свойству элемента.

Существуют два возможных результата поиска:

• поиск оказался удачным, т.е. позволил определить положение элемента в массиве;

• поиск оказался неудачным, т.е. достигнут конец массива, но элемент с заданным свойством отсутствует.