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

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

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

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

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

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

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

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

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

• машинные:

  • высокого уровня;

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

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

• математические:

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

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

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

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

Существуют некоторые договорённости о том, какие именно функции считаются эквивалентными.

Договоренности.

Определение. Функция f(n) и g(n) называются эквивалентными и обозначаются, как f(n) g(n), если выполняется хотя бы одно из двух условий:

либо

Мы будем пользоваться вторым определением выполнения эквивалентности как наиболее общим.

Пример: эквивалентны по условиям 1) и 2);

по 1) условию не эквивалентны, но эквивалентны по 2) условию.

Определение. Функции f(n) пренебрежимо мала по сравнению с функцией и g(n) обозначается f(n)<<g(n) или f(n) = o(g(n)), если выполняется условие .

2ⁿ >> n² (показательная функция растет быстрее, чем степенная).

n! >> aⁿ >> n^a >> log₂n, где n > 1, a > 0.

Теорема: n! >> aⁿ >> n^a , (a > 0) >> log₂n

Без доказательства.

Договоренность. В дальнейшем под log n будем подразумевать log₂n.