Рассказ про алгоритмическую сложность, классы P и NP, и про NP-полноту

[Amicus Plato]

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

Что же такое сложность алгоритма? На самом деле, понять это интуитивно довольно легко.
Алгоритмическая сложность — это зависимость времени исполнения алгоритма от длины входных данных.
То есть, конечно же очевидно, что если нам нужно что-то найти во входных данных или что-то переставить местами, то чем больше количество информации на входе, тем больше времени понадобится, чтобы получить результат.
"Время" здесь величина довольно абстрактная. Естественно, она (эта величина) должна быть универсальной, и не зависеть от типа и производительности компьютера или иного устройства, а также от других частностей. Измеряется она числом элементарных шагов. Сейчас поясню, что это такое.

Думаю, каждый согласится с тем, что любую (и не только вычислительную) задачу можно решать миллионом способов, но, как правило, лишь один (реже несколько) из них будут оптимальными.
Вот, например, возьмем задачу, которую можно решить полным перебором (пример не мой): нахождение фамилии в телефонном справочнике. Можно просматривать страницу за страницей, пока мы наконец не наткнемся на того, кого искали.
Однако же мало кто будет искать именно так. Нас спасает то, что фамилии упорядочены по алфавиту. Достаточно открыть справочник приблизительно посередине, и сразу станет ясно, в какой из двух половин надо искать. Таким образом, область поиска сразу сокращается вдвое. Если мы нужную половину откроем опять посередине, то на втором шаге нам останется лишь четверть справочника. Применяя такой нехитрый метод, мы двигаемся семимильными шагами.
(Кстати, так будет действовать "безмозглый компьютер", если его запрограммировать должным образом. Казалось бы, человеку сделать это быстрее, потому что он представляет, в начале алфавита нужная ему буква, в середине, или в конце, и поэтому он в состоянии открыть справочник сразу более точно, а не начинать с середины. Но, как оказывается, таким методом отбрасываются как максимум два-три (если повезет) первых шага, а дальше приходится использовать всё тот же алгоритм).

Таким образом, задача поиска фамилии в телефонном справочнике (в самом худшем случае) повторится столько раз, сколько мы можем делить число страниц пополам.
Т.е. если справочник у нас имеет n страниц, то в худшем случае пополам придется делить
2•2•...•2=2^m(>=n) раз, где m — такая степень двойки, что 2^m — минимальное число такого вида, превосходящее n, или равное ему.
Люди, близкие к математике или информатике фыркнут и скажут, что уже давно надо было перейти к логарифмам. Сейчас и перейду.
То самое искомое число m как раз и будет логарифмом по основанию 2 от длины входной информации n.
Т.е. log₂ n = m
Таким образом, чтобы пролистать справочник из тысячи страниц, нам нужно раскрыть его:
log₂ 1000 ≈ 10 раз.
(Потому что 2¹⁰=1024)
Если, предположим, наш справочник вдвое толще, и составляет более 2000 страниц, то нам придется его открыть всего лишь на один раз больше!
Если страниц у нас будет сто тысяч, понадобится всего лишь около 17 открываний!

Аналогично устроены некоторые численные методы! Самый похожий и один из самых распространенных (по крайней мере, в учебных целях): деление отрезка пополам.
Этот алгоритм один в один повторяет наши действия со справочником. Представьте себе, что нам нужно приблизительно найти корень алгебраического уравнения. То есть такое значение х, при котором f(x)=0, где f(x) и есть наше уравнение (какое-нибудь суперсложное, нерешаемое аналитически) Нам достаточно найти два значения х1 и х2, для которых f(x) имеет разные знаки. Предположим, f(x1)>0, а f(x2)<0. Ясно, что между ними лежит по крайней мере одно (хотя может быть и три и пять, и любое нечетное число) искомое нами значение х0, при котором и достигается равенство: f(x0)=0. Правильно? Нельзя же из плюса перескочить в минус, не побывав в нуле, при условии, конечно, что функция, описываемая уравнением, непрерывна на рассматриваемом отрезке!
И вот, это самое х0 мы и будем искать как фамилию в справочнике.
Поделим отрезок пополам и найдем знак нашего уравнения в серединной точке отрезка х3. Если f(x3)>0 (т.е. знак совпал со знаком f(x1)), то на половине отрезка [x1, x3] перехода через ноль не произошло. Таким образом, область поиска сократилась вдвое: остался отрезок [x3, x2], который на следующем шаге тоже поделится пополам. И так далее. Таким образом, за логарифмическое время можно найти корень уравнения с любой наперед заданной точностью.
Есть еще немного отличающийся (или много (или вообще не отличающийся) — пишу по памяти, а она имеет тенденцию привирать) метод пристрелки. Называется он так потому, что имитирует пристрелку орудия к цели. Мы не знаем корня, и в первый раз стреляем очень приблизительно. Но как только мы обстреляли корень с двух сторон: f(x)<0 — недолет, f(x)>0 — перелет, то каждый раз мы вводим в прицел коррективы и стреляем точнее, пока не попадем в сколь угодно малую окрестность корня.

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

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

(Это было только введение. Продолжение следует)

UPD: В комментариях важное дополнение сделал  Хранитель печати. Он привел основные классы сложности с их описанием.

@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato

Comments

[Хранитель печати]

Множество вычислительных проблем, для которых существуют алгоритмы, схожие по сложности, называется классом сложности.

Здесь можно заметить, что для одной и той же проблемы могут существовать алгоритмы, различные по сложности. В таком случае данное определение становится дуальным, что не есть хорошо (корректнее говорить о сложности алгоритма, а не задачи).
Вообще говоря, сложность алгоритма принято обозначать как О (читается "О-большое"), это так называемая О-нотация.
Наиболее часто встречающиеся классы сложности в зависимости от числа входных данных N таковы (в порядке нарастания сложности, т.е. увеличения времени работы алгоритма, при стремлении N к бесконечности):
О(1) - количество шагов алгоритма не зависит от количества входных данных. Обычно это алгоритмы, использующие определённую часть данных входного потока и игнорирующие все остальные данные. Например, Чистка 1квадратного метра ковра вне зависимости от его размеров.
О(log N) - логарифмический алгоритм. Главным образом, в эту категорию попадают алгоритмы поиска
О(N) - алгоритм линейной сложности. Например, просмотр обложки каждой поступающей книги - то есть для каждого входного объекта выполняется только одно действие
О(N log N) - специального названия не имеет. Такую сложность имеют алгоритмы быстрой сортировки, сортировки слиянием и "кучной" сортировки.
O(N²) - квадратичные алгоритмы. В основном, все простейшие алгоритмы сортировки
O(N^x) - полиномиальные алгоритмы
O(X^N) - экспоненциальные алгоритмы
О(N!) - факториальные алгоритмы, в основном, используются в комбинаторике для определения числа сочетаний, перестановок.
Конечно, если посмотреть на вышеприведённые записи, на первый взгляд, О(1) - самый лучший алгоритм. Но это не всегда так! Всё определяется числом входных данных. Константное время, требуемое для исполнения алгоритма сложности О(1) может оказаться во много раз больше, чем даже О(N!) при малом числе входных данных. Хотя, естественно, ничто не сравнится с О(1) при N, стремящемся к бесконечности.
Поэтому при программировании алгоритмов требуется оценить как трудоёмкость решения (более быстрые алгоритмы, как правило, требуют большей оптимизации кода, иногда менее устойчивы и уж как пить дать существенно тяжелее для проверки), так и класс задач, т.е. оценить максимальный объём входных данных - и уже исходить из полученных соотношений. Следует помнить, что выражение "Цель оправдывает средства" далеко не всегда применимо при реализации алгоритмов

[Amicus Plato]

Хранитель печати
О!
Вот спасибо!
Это прямо как раз то, что нужно для продолжения!

[капитан няшенька]

учусь на архитектора. понятия не имею как мне это может пригодиться, но ужасно интересно!

[Amicus Plato]

Nazarova Varvara
ну... одно и то же знание для разных людей может быть и утилитарным, и "чистым", лишенным прикладной ценности, но от этого не менее интересным ))))
спасибо))