Главная | Обратная связь

Понятие сложность алгоритма.

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

Для выяснения истины, в теории рассматриваются алгоритмы решения не конкретных, а так называемых, массовых задач. Массовая задача представляется как бесконечная серия индивидуальных задач. Индивидуальная же задача характеризуется объемом входных данных, требуемых для решения этой задачи. При этом, если размер индивидуальной задачи - некое натуральное число n, то сложность алгоритма решения массовой задачи становится функцией от n.

Для начала, рассмотрим алгоритм простого перебора всех двоичных ключей длины n. Поскольку очевидно, что количество таких ключей - 2 в степени n, то в данном алгоритме 2 в степени n шагов. Иначе говоря, сложность этого алгоритма равна 2 в степени n. Такой алгоритм является вариантом простого перебора и называется экспоненциальным алгоритмом.

Рассмотрим теперь алгоритм умножения столбиком двух n-значных чисел. Он состоит из n в степени 2 умножений однозначных чисел, и его сложность, измеренная количеством таких умножений, естественно равна n в степени 2. Такой алгоритм называют - полиномиальный алгоритм.

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

Нахождение точной зависимости для конкретной программы это очень сложная задача. По этой причине обычно ограничиваются асимптотическими оценками конкретного алгоритма, то есть описанием его примерного поведения при больших значениях основного параметра. Иногда для асимптотических оценок используют традиционное отношение О (О большое) между двумя функциями. Например, функция f(n) = n2/2 + 3n/2 + 1 возрастает приблизительно так же как n2/2 (мы отбрасываем медленно растущее слагаемое 3n/2+1). Константный множитель 1/2 также отбрасываем и получаем асимптотическую оценку для алгоритма, которая обозначается как O(n2).

Здесь мы приведем сравнительную таблицу времен выполнения алгоритмов с различной сложностью и разберемся, почему с увеличением быстродействия компьютеров важность использования быстрых алгоритмов значительно возрасла.

Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности log n,n ,n в степени 2 и 2 в степени n. Предположим, что второй из этих алгоритмов требует для своего выполнения на неком компьютере при значении опеределенном параметра (например 10 в степени 3) ровно одну минуту времени. В этом случае время выполнения этих четырех алгоритмов на том же компьютере будут выглядеть примерно так:

Итак, подведем итог. C увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлимое время. Таким образом, увеличивается среднее значение величины , и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма!