Понятие вычислительной сложности

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

Пример

«найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей ( ), так как открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счет сортировки имен по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за раз (открываний книги). При увеличении объема страниц до ста тысяч, проблема все еще решается за заходов. (См. Двоичный поиск.)

Машина Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: q_ia_j→q_i1a_j1d_k(если головка находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то головка переходит в состояние q_i1, в ячейку вместо a_j записывается a_j1, головка делает движение d_k, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <q_i, a_j> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил).

NP-полные задачи

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

Вычислимость

НЕ ВСЯКИЙ АЛГОРИТМ МОЖЕТ ПРИВЕСТИ К ОТВЕТУ И ЗАДАЧИ ДЛЯ КОТОРЫХ МЫ НЕ МОЕМ СОСТАВИТЬ АЛГОРИТМЫ РЕШЕНИЯ НАЗЫВАЮТ НЕ ВЫЧЕСЛЕННЫМИ

Линейная сложность

Определение: Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом:

• Если – нулевая последовательность , то
• Если не существует РСЛОС, который генерирует , то равно бесконечности.
• Иначе, есть длина самого короткого РСЛОС, который генерирует .

Полиномиальная вычислительная сложность

Определение

В теории алгоритмов классом P (от англ. polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включён в более широкие классы сложности алгоритмов.

Пример

Примерами задач из класса P являются целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц, выяснение связности графов, сортировка множества из n чисел, нахождение эйлерова цикла на графе из m рёбер, обнаружение в тексте длиной n некоторого слова, построение покрывающего дерево минимальной стоимости, линейное программирование и некоторые другие.