(Всё, что я здесь напишу, будет изложено неформально. Постараюсь избежать каких бы то ни было определений, и, тем более, сложных выводов... Хотя это будет совсем не просто)))
Что же такое сложность алгоритма? На самом деле, понять это интуитивно довольно легко.
Алгоритмическая сложность — это зависимость времени исполнения алгоритма от длины входных данных.
То есть, конечно же очевидно, что если нам нужно что-то найти во входных данных или что-то переставить местами, то чем больше количество информации на входе, тем больше времени понадобится, чтобы получить результат.
"Время" здесь величина довольно абстрактная. Естественно, она (эта величина) должна быть универсальной, и не зависеть от типа и производительности компьютера или иного устройства, а также от других частностей. Измеряется она
числом элементарных шагов. Сейчас поясню, что это такое.
читать дальшеДумаю, каждый согласится с тем, что любую (и не только вычислительную) задачу можно решать миллионом способов, но, как правило, лишь один (реже несколько) из них будут оптимальными.
Вот, например, возьмем задачу, которую можно решить полным перебором (пример не мой): нахождение фамилии в телефонном справочнике. Можно просматривать страницу за страницей, пока мы наконец не наткнемся на того, кого искали.
Однако же мало кто будет искать именно так. Нас спасает то, что фамилии упорядочены по алфавиту. Достаточно открыть справочник приблизительно посередине, и сразу станет ясно, в какой из двух половин надо искать. Таким образом, область поиска сразу сокращается вдвое. Если мы нужную половину откроем опять посередине, то на втором шаге нам останется лишь четверть справочника. Применяя такой нехитрый метод, мы двигаемся семимильными шагами.
(Кстати, так будет действовать "безмозглый компьютер", если его запрограммировать должным образом. Казалось бы, человеку сделать это быстрее, потому что он представляет, в начале алфавита нужная ему буква, в середине, или в конце, и поэтому он в состоянии открыть справочник сразу более точно, а не начинать с середины. Но, как оказывается, таким методом отбрасываются как максимум два-три (если повезет) первых шага, а дальше приходится использовать всё тот же алгоритм).
Таким образом, задача поиска фамилии в телефонном справочнике (в самом худшем случае) повторится столько раз, сколько мы можем делить число страниц пополам.
Т.е. если справочник у нас имеет n страниц, то в худшем случае пополам придется делить
2•2•...•2=2m(>=n) раз, где m — такая степень двойки, что 2m — минимальное число такого вида, превосходящее n, или равное ему.
Люди, близкие к математике или информатике фыркнут и скажут, что уже давно надо было перейти к логарифмам. Сейчас и перейду.
То самое искомое число m как раз и будет логарифмом по основанию 2 от длины входной информации n.
Т.е. log2 n = m
Таким образом, чтобы пролистать справочник из тысячи страниц, нам нужно раскрыть его:
log2 1000 ≈ 10 раз.
(Потому что 210=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: В комментариях важное дополнение сделал
Хранитель печати. Он привел основные классы сложности с их описанием.