Центральным понятием курса будет трудоемкость алгоритма. Рассмотрим это понятие подробнее.
Пусть на входе некоторого алгоритма имеется информация объема n (например, n – длина массива, размер матрицы СЛАУ, длина перемножаемых чисел и т.п.), а на выходе ответ – результат обработки входной информации.
Определение: Трудоемкость алгоритма Т(n) – максимально возможное количество действий для решения данной задачи среди всех возможных входов длины n.
Замечание: Иногда под сложностью алгоритма подразумевают не максимальное количество операций, а среднюю трудоемкость. Порядок средней и максимальной трудоемкостей, как правило, одинаков.
Характеристики алгоритма:
Т(n) – (от англ. Time) – количество операций, необходимых для обработки информации объема n.S(n)– (от англ. Spaсe) – объём необходимой памяти для обработки информации.
Алгоритмы решения задачи могут быть написаны на разных языках:
– низкого уровня;
– машинные коды;
– конечные автоматы;
– рекурсивные функции;
Все эти языки эквивалентны с точки зрения набора решаемых задач (любая задача, реализованная на одном языке, может быть переписана на другой), но они неэквивалентны с точки зрения трудоемкости. Трудоемкость алгоритма, реализованного на одном языке, может существенно отличаться от того же алгоритма, записанного на другом языке.