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

Для практики недостаточно знать, что задача алгоритмически разрешима. Т. к. ресурсы ЭВМ (ОП и время процессора) ограничены, следует выбирать из эквивалентных алгоритмов наиболее эффективный. Для оценки эффективности введено понятие сложности.

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

- это время T, необходимое для его выполнения в зависимости от исходных данных. Временнáя сложность алгоритма T = k·t, где k – кол-во вычислительных действий, t – время выполнения одного действия.

n – это размерность задачи (для линейного массива – размер массива). T(n) – зависимость времени от объема входных данных. Поведение T п ри увеличении n н азывается теоретической сложностью – O( f(n) ).

Сравнительная оценка сложности алгоритмов Сложность O(f(n)) Тип зависимости Значение при n=2 10 = =1024 O(n) Линейная 1024 O(n·log 2 n) Логарифмическая O(n2)O(n3)O(n2)O(n3) Полиномиальная O(2 n ) Экспоненциальная

Задача Дано: два алгоритма А 1 и А 2, решающих одну и ту же задачу размерности n=10 6. А 1 имеет сложность O 1 (n 2 ) и выполняется на суперкомпьютере с быстродействием 10 8 оп/с; А 2 имеет сложность O 2 (n·log 2 n) и выполняется на обычном компьютере с быстродействием 10 6 оп/с. Требуется: найти время решения задачи t 1 - ?, t 2 - ?

Решение t 1 = / 10 8 = 10 4 с 2,8 ч t 2 = 10 6 ·log / 10 6 = 6 ·log с Вывод: Р азработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники!