1.1 Основные понятия

Центральным понятием курса будет трудоемкость алгоритма. Рассмотрим это понятие подробнее.

Пусть на входе некоторого алгоритма имеется информация объема n (например, n – длина массива, размер матрицы СЛАУ, длина перемножаемых чисел и т.п.), а на выходе ответ – результат обработки входной информации.

Определение: Трудоемкость алгоритма Т(n) – максимально возможное количество действий для решения данной задачи среди всех возможных входов длины n.

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

Характеристики алгоритма:

Т(n) – (от англ. Time) – количество операций, необходимых для обработки информации объема n.

S(n)– (от англ. Spaсe) – объём необходимой памяти для обработки информации.

Алгоритмы решения задачи могут быть написаны на разных языках:

    машинные:    – высокого уровня;

                        – низкого уровня;

                        – машинные коды;

    математические:  – математические реализации (машины Тьюринга);

                                        – конечные автоматы;

                                        – рекурсивные функции;

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