Формула которая показывает экспоненциальную сложность алгоритма

Saved searches

Use saved searches to filter your results more quickly

Cancel Create saved search

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

�� Подборка алгоритмов, которые правят миром

goavengers/go-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Switch branches/tags
Branches Tags
Could not load branches
Nothing to show
Could not load tags
Nothing to show

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Cancel Create

• Local
• Codespaces

HTTPS GitHub CLI
Use Git or checkout with SVN using the web URL.
Work fast with our official CLI. Learn more about the CLI.

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

Latest commit message
Commit time

README.md

Подборка алгоритмов, которые правят миром

Вместе мы разберемся!

Содержание

Вступление

1. Вчём цель?
2. Оценка сложности алгоритмов, или Что такое Big O
3. Закрепление примерами
4. Заключение
5. Производительность относительно данных

Алгоритмы сортировки

1. Пузырьковая сортировка
2. Сортировка выборкой
3. Сортировка вставками
4. Пирамидальная сортировка
5. Сортировка слиянием
6. Быстрая сортировка

Алгоритмы поиска

1. Поиск в глубину
2. Поиск в ширину
3. Двоичный поиск
4. Линейный поиск

Прежде чем начать, зачем мне изучать концепцию Big O?

• Концепцию Big O необходимо понимать, чтобвы видеть и исправлять неоптимальный код.
• Ни один серьезный проект или собеседование не могут обойтись без вопросов о Big O.
• Не понимание Big O ведет к серьезной потери производительности ваших алгоритмов.

Вчём цель?

• Цель проста — научиться понимать концепцию Big O.

Big O (в рамках Computer Science) показывает верхнюю границу зависимости между входными параметрами функции и количеством опрераций, которые выполнит процессор. Т.е, показывает зависимость, допустим, между массивом в 1000 элементов и количеством тактов, которое необходимо выполнить процессору, чтобы обработать эти 1000 элементов.

Вступление, это не относится непосредственно к языку программирования Golang, но почитать или освежить память никому не помешает

Оценка сложности алгоритмов, или Что такое Big O.

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n. Тогда говорят, что временная сложность этого алгоритма равна О(n3), т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).

O(1) — константная сложность

Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Следует помнить, однако, что единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени. Он может потребовать и микросекунду, и год. Важно то, что это время не зависит от входных данных.

func GetCount(items []int) int < return len(items) >

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Если линейный алгоритм обрабатывает один элемент пять миллисекунд, то мы можем ожидать, что тысячу элементов он обработает за пять секунд.

Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.

func GetSum(items []int) int < sum := 0 for _, item := range items < sum += item > return sum >

O(log n) — логарифмическая сложность

Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. (Прим. пер.: в анализе алгоритмов по умолчанию используется логарифм по основанию 2). Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Метод Contains бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n^2) — квадратичная сложность

Время работы алгоритма с порядком роста O(n^2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются. Например, если массив из тысячи элементов потребует 1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, квадратичный алгоритм будет обрабатывать миллион элементов 32 года. Даже если он будет в сто раз быстрее, работа займет 84 дня.

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n^2.

// не совсем яркий пример: содержит ли вектор (своеобразный массив) A размера n два одинаковых значения func DuplicateExist(A []int) bool < n := len(A) for i :=0; i  n; i++ < for j:= 0 j  n; j++ < if i != j && A[i] == A[j] < return true > > > return false >

Два вложенных цикла дадут нам асимптотику вида f(n) = O(n^2).

Практическая рекомендация: простые программы можно анализировать с помощью подсчёта в них количества вложенных циклов:

• Одиночный цикл в n итераций даёт f(n) = O(n).
• Цикл внутри цикла — f(n) = O(n^2).
• Цикл внутри цикла внутри цикла — f(n) = O(n^3). И так далее.

Практическая рекомендация: если у нас имеется серия из последовательных for-циклов, то асимптотическое поведение программы определяет наиболее медленный из них. Два вложенных цикла, идущие за одиночным, асимптотически тоже самое, что и вложенные циклы сами по себе. Говорят, что вложенные циклы доминируют над одиночными.

f(n) = O(n^2) func Asymptotic() < for i := 0; i  N; i ++ < // do stuff > // доминирующая сложность for i := 0; i  N; i++ < for j := 0; j  N; j++ < // do stuff > > >

Примечания:

• Константы всегда отбрасываются: 2n => O(n), 6n^2 => O(n^2), потому что концепция Big O описывает скорость выполнения алгоритма, стремящийся к бесконочности, 2 бесконечности, 5 бесконечностей — это одна и та же бесконечность.

Полезные ресурсы

Что мы измеряем?

При измерении сложности алгоритмов и структур данных мы обычно говорим о двух вещах: количество операций, требуемых для завершения работы (вычислительная сложность), и объем ресурсов, в частности, памяти, который необходим алгоритму (пространственная сложность).

Алгоритм, который выполняется в десять раз быстрее, но использует в десять раз больше места, может вполне подходить для серверной машины с большим объемом памяти. Но на встроенных системах, где количество памяти ограничено, такой алгоритм использовать нельзя.

Закрепление примерами

1. Как вы думаете, какая сложность у двух следующих алгоритмов?

func sum(n int) int < if n == 1 < return 1 > return n + sum(n - 1) >

func pairSumSequence(n int) int < sum := 0 for i := 0; i  n; i++ < sum += pairSum(i, i + 1) > return sum > func pairSum(a, b int) int < return a + b >

Ответ: у обеих алгоритмов линейное быстродействие O(n)

2. Какой код выполнится быстрее?

const MaxInt = int(MaxUint >> 1) const MinInt = -MaxInt - 1 // Первый func MaxAndMin(n []int) (int, int) < for _, x := range n < if x  MinInt < min = x > if x > MaxInt < max = x > > return min, max > // второй func MaxAndMinSecond(n []int) (int, int) < for _, x := range n < if x  MinInt < min = x > > for _, x := range n < if x > MaxInt < max = x > > return min, max >

Логично, что первая 1 цикл и один проход по циклу и действительно, если смотреть на команды процессора второй пример является медленее. Но в данном случае это было бы неверно. Концепция Big O показывает как ведут себя эти алгоритмы.

Ответ: у обоих алгоритмов сложность O(n)

3. Как быть со сложностью O(n^2 + n)?

Надо понимать как отсеивать неважную сложность:

• N не является константой, следовательно ее нельзя отбросить
• Но мы понимаем, что O(n^2 + n^2) == O(n^2)
• Так же мы понимаем, что O(n^2) > O(n) , следовательно если она меньше то не влияет на сложность алгоритма

Ответ: Сложность данного алгоритма O(n^2)

Несколько примеров, чтобы осталось в голове:

• O(n^2 + n) мы уже знаем что это O(n^2)
• O(n + log n) это O(n) , т.к. O(log n) гораздо меньше O(n)
• O(5 * 2^n + 10 * 2^100) константы мы помним можно отбрасывать -> O(2^n * 2^100) = O(2^n) , т.к. экспоненциальное время O(2^n) намного больше степенной.
• O(n^2 + B) — считаете что O(n^2) ? На самом деле ответ будет O(n^2 + B) , т.к. мы ничего не можем сказать о B и мы не можем выбросить ее из нашей сложности.

4. Откуда берется сложность алгоритма O(log n)?

Время выполнения log n на примере бинарного поиска, когда каждый раз берется половина элементов:

• 2^k = N // 2^4 = 16
• k = log2 n
• O(k) = O(log2 n)
• O(k) = O(log n) , отбрасывае двойку, т.к. мы помним что она является константой и ее можно отбросить

Ответ: для алгоритма, где на каждой итерации берется половина элементов сложность будет включать O(log n) , она так же может быть O(A * log n) или O(A + B * log n) , главное что каждый раз берется половина элементов.

5. Какая сложность у следующего алгоритма?

func foo(n []int) < for n-раз for n-раз >

Ответ: O(n + n ) = O(n)

6. Какая сложность у следующего алгоритма?

func foo(n []int) < for n-раз < for n-раз < >> >

Ответ: O(n * n) = O(n^2)

7. Какая сложность у следующего алгоритма?

func foo(n []int) < for i := 0; i  len(n); i++ < for j := i; j  len(n); j++ < // do stuff > > > // всевдо func foo(n []int) < for n-раз < for n, n-1, n-2, n-3, . , 6, 7 - раз > >

• Код внешнего цикла выполняется n-раз
• Код внутреннего цикла выполняется n, n-1, n-2 и т.д. раз
• Тогда сложность можно описать как: O(n + (n — 1) + (n — 2) + . + 2 + 1) , как его упросить?

Ответ: Сложность алгоритма O(n^2)

8. Какая сложность у следующего алгоритма?

func foo(a, b []int) < for _, x := range a < for _, z := range b < // do stuff > > > func foo(a, b []int) < for len(a)-раз < for len(b)-раз < // do stuff > > >

Ответ: O(a * b)

9. Какая сложность у следующего алгоритма?

func foo(a, b []int) < for _, x := range a < for _, z := range b < for k := 0; k  100000; k++ < // do stuff > > > >

Ответ: O(a * b), почему? 100000 это конечно много, но это константа и ее можно отбросить, помни это

10. Какая сложность у следующего алгоритма?

func reverse(n []int) < length := len(n) for i := 0; i  length / 2; i++ < other := length - i - 1 temp := n[i] n[i] = n[other] n[other] = temp > > func reverse(n []int) < for n / 2 раз >

Думаете O(log n)? Казалось бы да, но нет.

Ответ: O(n/2), т.к. мы просто один раз берем половину элементов массива и итерируем их, скажем было 100 элементов взяли половину — 50, для Big O это все те же n элементов, следовательно сложность алгоритма O(n)

Какие выводы мо можем теперь сделать?

• Big O показывает темп роста функции. Следовательно мы можем не учитывать константы и «неважную сложность».
• Последовательность действие — это сложение, вложенные действия — умножение.
• Для алгоритмов, где на кажлой итерации берется половина элементов сложность\будет включать O(log n)

Производительность относительно данных

Ниже приведен список некоторых наиболее часто используемых обозначений Big O и их сравнение производительности с различными размерами входных данных.

Big O Notation	Расчеты для 10 элементов	Расчеты для 100 элементов	Расчеты для 1000 элементов
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

About

�� Подборка алгоритмов, которые правят миром

‍ Теория сложности

Раз­но­об­раз­ные алго­ритмы для реше­ния самых раз­лич­ных задач повсе­местно встре­чаются как в науке и тех­нике, так и в обы­ден­ной жизни (хотя в послед­нем слу­чае они всё чаще и чаще нахо­дятся «под капо­том» и рядо­вому поль­зо­ва­телю видны плохо). Неко­то­рые из них, вклю­чая наи­бо­лее важ­ные, упоми­наются в насто­ящем сбор­нике. В этой ста­тье мы пого­во­рим об общей дис­ци­плине, кото­рая занима­ется изу­че­нием эффек­тив­но­сти или, если угодно, каче­ства алго­ритмов вне зави­симо­сти от их вида и про­ис­хож­де­ния. Пре­жде всего надо дого­во­риться о классе изу­ча­емых объек­тов, т. е. соб­ственно алго­ритмов. Еди­ного мне­ния на этот счёт нет. Само слово «алго­ритм» про­ис­хо­дит от имени вели­кого пер­сид­ского учё­ного аль‐­Хо­резми, в IX веке опи­савшего пра­вила обраще­ния с позици­он­ной системой счис­ле­ния (любопытно, что слово «алгебра» про­ис­хо­дит из того же сочи­не­ния). После этого в тече­ние долгого времени под алго­ритмами понима­лось искус­ство и пра­вила счёта; алго­ритмы, опе­ри­рующие с целыми или раци­о­наль­ными чис­лами мы будем назы­вать чис­ло­выми. Сле­дующей ступе­нью общ­но­сти являются алго­ритмы, рабо­тающие с про­из­воль­ными дис­крет­ными дан­ными: графами, мас­си­вами, тек­стами, рас­пи­са­ни­ями и т. д. Это алго­ритмы в строго матема­ти­че­ском смысле этого слова. Они были опре­де­лены и впер­вые изу­чены в рабо­тах вели­ких матема­ти­че­ских логи­ков прошлого сто­ле­тия, таких, как К. Гёдель, А. А. Мар­ков, П. С. Нови­ков, А. Тью­ринг, А. Чёрч, создавших строгую тео­рию вычис­лимо­сти, и это именно тот класс алго­ритмов, кото­рый исполь­зу­ется в современ­ных устройствах. Нако­нец, алго­ритмы можно понимать и в наи­бо­лее широ­ком смысле, как набор кон­крет­ных и пол­но­стью опре­де­лён­ных пра­вил, выпол­не­ние кото­рых поз­во­лит добиться постав­лен­ной цели за конеч­ное время. Основ­ное положе­ние тео­рии слож­но­сти алго­ритмов, грубо говоря, состоит в том, что не все алго­ритмы равны с точки зре­ния их прак­ти­че­ской при­год­но­сти, при­чём эти раз­ли­чия могут отно­ситься не только к алго­ритмам, сто­ящим на раз­ных ступень­ках лест­ницы, обри­со­ван­ной в преды­дущем абзаце, но даже к алго­ритмам для одной и той же задачи. Более того, «каче­ство» алго­ритмов можно изме­рять неко­то­рой «функцией слож­но­сти», что, соб­ственно, и при­во­дит к стро­гой матема­ти­че­ской тео­рии. Мы попыта­емся про­ил­лю­стри­ро­вать её основ­ные идеи на про­стом модель­ном при­мере. Рас­смот­рим задачу нахож­де­ния наи­большего общего дели­теля $\mbox(a,b)$ нату­раль­ных чисел $a$ и $b$ ($aПер­вый алго­ритм (совсем при­ми­тив­ный). Пере­би­раем все числа от $a$ до 1 в порядке убы­ва­ния (т. е. начи­ная с $a$) , пока не натолк­нёмся на нуж­ное. Вто­рой алго­ритм (после неко­то­рого раз­думья). Давайте лучше после­до­ва­тельно делить $a$ на 2, 3, 4, и про­бо­вать $a/2$, $a/3$, $a/4$ (име­ется в виду, что если $a/k$ не явля­ется целым, мы его про­пус­каем, а если оно целое, про­буем поде­лить на него $b$) и т. д., пока не добе­рёмся при­мерно до $\sqrt a$. Если нам повезло (а это заве­домо слу­чится при $\mbox(a,b)\geq\sqrt a$) , то хорошо, а если нет, то пере­хо­дим к пер­вому спо­собу, но на этот раз начи­ная с $\sqrt a$, а не с $a$. Тре­тий алго­ритм (для матема­ти­че­ски про­дви­ну­тых). Раз­ложим $a$ и $b$ на про­стые множи­тели: $a=p_1^\>…\> p_k^>$ и $b=p_1^\>…\> p_k^>$ (неко­то­рые степени здесь могут быть нуле­выми). Тогда наи­больший общий дели­тель вычис­ля­ется по нехит­рой формуле $$ d= p_1^<\min(d_1,\>e_1)>\>p_2^<\min(d_2,\>e_2)>\>…\> p_k^<\min(d_k,\>e_k)>. $$ Для того, чтобы разум­ным спо­со­бом срав­ни­вать раз­лич­ные под­ходы, оче­видно, нужна неко­то­рая общая «линейка» (или «мера»). Можно пытаться исполь­зо­вать в каче­стве меры про­сто число сде­лан­ных попыток, тогда сразу видно, что в наи­худ­шем слу­чае пер­вому алго­ритму пона­до­бится порядка $a$ попыток, в то время как вто­рому — порядка $2\sqrt a$, что уже явля­ется ощу­тимым прогрес­сом. Но как их срав­ни­вать с тре­тьим алго­ритмом, исполь­зующим совсем другие (и более про­дви­ну­тые) идеи? Ситу­ации, когда хорошие алго­ритмы движутся к цели околь­ными путями, встре­чаются сплошь и рядом; соб­ственно для их ана­лиза тео­рия алго­ритмов и суще­ствует. Поэтому понятно, что иско­мая линейка должна быть уни­вер­саль­ной и при­год­ной для любого алго­ритма, неза­ви­симо от выбран­ного им пути реше­ния задачи. Ока­зы­ва­ется, что даже если нас инте­ре­суют только тео­ре­тико-чис­ло­вые задачи типа нашего модель­ного при­мера, дать рабо­то­спо­соб­ное опре­де­ле­ние их слож­но­сти пол­но­стью в терми­нах чисел затруд­ни­тельно — слиш­ком много раз­ных идей и кра­си­вой матема­тики вовле­чено в уже имеющи­еся алго­ритмы. Многие из них даже не являются чис­ло­выми в нашем смысле, т. е. исполь­зуют для своей работы объекты дру­гой при­роды. По этой при­чине уни­вер­саль­ная мера может быть вве­дена лишь на сле­дующей ступени общ­но­сти в рам­ках клас­си­че­ской тео­рии вычис­лимо­сти, и по‐­на­уч­ному она назы­ва­ется чис­лом так­тов рабо­тымашины Тью­ринга — абстракт­ного вычис­ли­тель­ного устройства, пред­ложен­ного вели­ким бри­тан­ским матема­ти­ком А. Тью­рингом в 1936 году. На инту­и­тив­ном уровне это число элемен­тар­ных (т. е. далее нераз­ложимых) шагов, кото­рые тре­бу­ется предпри­нять для достиже­ния постав­лен­ной цели. В слу­чае клас­си­че­ской машины Тью­ринга это опе­рации совсем при­ми­тив­ные: сдви­нуться по вычис­ли­тель­ной ленте на одну позицию влево или вправо, про­честь или пере­за­пи­сать обо­зре­ва­емый сим­вол и т. д. Но чита­тель, немного зна­комый с программи­ро­ва­нием, может без осо­бого ущерба для понима­ния предпо­лагать, что мы под­счи­ты­ваем число выпол­не­ний инструкций, содержащихся в программе, за всё время её работы. Именно число выпол­не­ний, а не число самих инструкций — послед­нее при­во­дит к так назы­ва­емой колмого­ров­ской слож­но­сти, кото­рую мы здесь не рас­смат­ри­ваем. Пого­во­рим теперь немного о роли слу­чая. Если мы ста­нем при­ме­нять наши алго­ритмы к $a=54 284 452$, $b=67 855 565$, то скажется это на их работе по‐раз­ному. Пер­вый и тре­тий спе­ци­фики $a$ и $b$ про­сто не заме­тят, и будут рабо­тать со своей обыч­ной про­из­во­ди­тель­но­стью, а вто­рой алго­ритм выдаст пра­виль­ный ответ $\mbox(a,b)=13 571 113$ с тре­тьей попытки. Озна­чает ли это, что он одно­значно лучше? Строго матема­ти­че­ский ответ на этот вопрос дать невозможно. Всё зави­сит от того, насколько часто исклю­чи­тельно хорошие или исклю­чи­тельно пло­хие при­меры встре­чаются в инте­ре­сующем нас в дан­ный момент кон­крет­ном при­ложе­нии. Хре­сто­ма­тий­ным при­ме­ром служит сим­плекс-метод, исполь­зу­емый (насколько автору известно) во всех современ­ных паке­тах линей­ного программи­ро­ва­ния для реше­ния опти­ми­за­ци­он­ных задач. Здесь ситу­ация строго обрат­ная (в срав­не­нии с при­ве­дён­ным при­ме­ром для вто­рого алго­ритма): исклю­чи­тельно пло­хие при­меры для сим­плекс-метода известны, но для их постро­е­ния надо хорошо поста­раться, и на прак­тике они не заме­чены. Наи­бо­лее матема­ти­че­ский под­ход к ана­лизу алго­ритмов состоит, конечно, в том, чтобы не полагаться на слу­чай и нали­чие исклю­чи­тельно хороших при­ме­ров про­сто игно­ри­ро­вать. Он назы­ва­ется тео­рией слож­но­сти в наи­худ­шем слу­чае (или иногда гаран­ти­ро­ван­ной слож­но­стью). Со всеми сде­лан­ными ого­вор­ками такой под­ход ока­зы­ва­ется вполне каче­ствен­ной и адек­ват­ной моде­лью в большин­стве инте­рес­ных ситу­аций — про­колы типа сим­плекс-метода (т. е. когда слож­ность в наи­худ­шем слу­чае опре­де­ля­ется исклю­чи­тельно пло­хими при­ме­рами) можно пере­счи­тать на паль­цах одной руки. Тре­бо­вать от матема­ти­че­ской модели большего про­сто нера­зумно. Чтобы разо­браться, в чём же этот под­ход состоит, заме­тим, что наи­бо­лее важ­ная и уни­вер­саль­ная информация о числе — это коли­че­ство зна­ков в его записи ($n$) . Скажем, в нашем при­мере $n=8$, если запись деся­тич­ная и $n≈ 25$, если она дво­ич­ная — отли­чие чуть больше, чем в три раза. Конеч­ная цель раз­ра­бот­чи­ков алго­ритмов — постро­ить алго­ритм, кото­рый гаран­ти­ро­ванно решает задачу за $f(n)$ элемен­тар­ных шагов, неза­ви­симо от того, какие именно $n$ ‐раз­ряд­ные числа ему даны (где $f$ — неко­то­рая функция, жела­тельно мед­ленно рас­тущая). Под­черк­нём, что $n$ — именно число зна­ков в записи числа, а не само это число; чтобы почув­ство­вать раз­ницу, доста­точно заме­тить, что число, выражающее число атомов в видимой части Все­лен­ной вполне умеща­ется на одной строчке, хотя и убо­ри­стым почер­ком. Раз­бе­рём ещё раз с этой точки зре­ния алго­ритмы для нашего модель­ного при­мера. Пер­вому алго­ритму в худ­шем слу­чае пона­до­бится порядка $f(n)≈ 10^n$ элемен­тар­ных опе­раций. Это про­из­ве­де­ние числа попыток на число опе­раций, необ­хо­димых для каж­дой из них, но поскольку для этого тре­буются лишь про­стые арифме­ти­че­ские действия (впро­чем, как выте­кает из ста­тьи ⁠ «Быст­рая арифме­тика» , даже для них ситу­ация не настолько про­ста, насколько кажется), вто­рой множи­тель ока­зы­ва­ется небольшим поли­номом от $n$, и по срав­не­нию с экс­по­ненци­аль­ными функци­ями им вполне можно пре­не­бречь. Знак при­ближён­ного равен­ства $≈$ вызван именно этим обсто­я­тельством. Вто­рой алго­ритм в наи­худ­шем слу­чае (хорошее упраж­не­ние — попытаться понять, в каком) потре­бует $f(n)≈ 10^$ опе­раций, так что он в самом деле слегка лучше пер­вого. Намного поучи­тель­нее ситу­ация с тре­тьим алго­ритмом. Понятно, что его успех в первую оче­редь зави­сит от сле­дующего вопроса: насколько быстро мы умеем рас­кла­ды­вать числа на про­стые множи­тели? Этот вопрос занимал матема­ти­ков с антич­ных времён, за тыся­че­ле­тия до того, как предпо­ложе­ние о том, что эффек­тив­ного спо­соба реше­ния задачи о раз­ложе­нии на про­стые множи­тели не суще­ствует, легло в основу большин­ства исполь­зу­емых в современ­ном мире крип­то­си­стем. Глу­боко вда­ваться в этот вопрос у нас, к сожа­ле­нию, возмож­но­сти нет (дан­ная тема заслужи­вает отдель­ной ста­тьи), поэтому отме­тим лишь, что наи­лучший из извест­ных сегодня алго­ритмов в наи­худ­шем слу­чае рабо­тает за время $f(n)=10^(\log_2 n)^>$, где $C>0$ — не слиш­ком большая кон­станта. Это уже суще­ственно лучше в срав­не­нии с $f(n)$ для пер­вого и вто­рого алго­ритмов, но функция всё равно рас­тёт экс­по­ненци­ально быстро. Давайте ещё немного поразмыш­ляем над тре­тьим алго­ритмом. По сво­ему виду он явля­ется све­де­нием одной задачи к дру­гой, а именно, задачи нахож­де­ния наи­большего общего дели­теля к задаче раз­ложе­ния чисел на про­стые множи­тели. Это озна­чает, что любой прогресс в реше­нии вто­рой задачи авто­ма­ти­че­ски вле­чёт рав­но­знач­ный прогресс в реше­нии пер­вой. Как мы уви­дим ниже, общее поня­тие сво­димо­сти одной задачи к дру­гой играет исклю­чи­тельно важ­ную роль в тео­рии слож­но­сти алго­ритмов. В программист­ских терми­нах оно соот­вет­ствует поня­тию проце­дуры или подпрограммы; надо, правда, ещё поза­бо­титься о том, чтобы проце­дура вызы­ва­лась «не слиш­ком часто» (в слу­чае тре­тьего алго­ритма — два раза) и для «не слиш­ком» больших зна­че­ний парамет­ров (в нашем слу­чае это про­сто исход­ные дан­ные $a$ и $b$) . В том, что каса­ется нахож­де­ния наи­большего общего дели­теля, пора пере­хо­дить к раз­вязке, многими чита­те­лями, по‐ви­димому, давно ожи­да­емой. «Начала» вели­кого древ­негре­че­ского матема­тика Евклида (около 300 года до н. э.) по праву счи­таются одной из вели­чайших книг в исто­рии чело­ве­че­ства, в кото­рой были заложены основы современ­ной геомет­рии (термины «евкли­дово про­стран­ство», «евкли­дова мет­рика» и др. вос­хо­дят к тек­сту «Начал»), и во многом всей современ­ной матема­тики вообще. Гораздо менее известно, что книга VII содержит опи­са­ние ста­рейшего из дошед­ших до нас алго­ритмов, кото­рый к тому же активно исполь­зу­ется и сегодня. Алго­ритм чет­вёр­тый и послед­ний (алго­ритм Евклида). Раз­де­лим $b$ на $a$ с остат­ком: $b=h\cdot a+r$, где $0\leq r\leq a-1$. После этого рекур­сивно при­ме­няем алго­ритм к паре $(r,a)$ : делим $a$ на $r$, $a=u\cdot r+s$ и заме­няем пару $(r,a)$ на $(s,r)$. Про­должаем действо­вать, пока не добе­рёмся до пары вида $(0,d)$. Вто­рое число в полу­чен­ной паре и будет искомым отве­том. Почему этот алго­ритм рабо­тает пра­вильно? И, даже если так, почему он рабо­тает быстро? Отве­тами на вопросы такого рода (когда они не вполне оче­видны, конечно) занима­ется спе­ци­аль­ный раз­дел тео­рии слож­но­сти, назы­ва­емый ана­ли­зом алго­ритмов. Алго­ритм Евклида рабо­тает пра­вильно, потому что $\mbox(a,b) = \mbox(r,a) =\mbox(s,r) =…$ Тем самым, наи­больший общий дели­тель явля­ется, как любят гово­рить матема­тики, инва­ри­ан­том дан­ной проце­дуры (срав­ните со ста­тьёй ⁠ «Игра в „15» ), а для заклю­чи­тель­ной пары $(0,d)$ он как раз и равен $d$. Быстро он рабо­тает потому, что все­гда имеет место соот­ноше­ние $(a+r)\leq\frac 23(a+b)$. Поэтому сумма чисел в паре убы­вает экс­по­ненци­ально и, в част­но­сти, алго­ритм заве­домо сой­дётся за $f(n)≈ 10n$ ите­раций, что явля­ется линей­ной функцией от числа зна­ков $n$ в записи $a$ и $b$. Результат ока­зы­ва­ется настолько впе­чат­ляющим по срав­не­нию с нашими преды­дущими под­хо­дами, что их можно было бы смело отне­сти к раз­ряду исто­ри­че­ских курьё­зов, если бы не то обсто­я­тельство, что алго­ритму Евклида уже порядка 2500 лет… Учи­ты­вая его про­стоту и эффек­тив­ность, алго­ритм Евклида и его обобще­ния широко исполь­зуются в наши дни, как в тео­ре­ти­че­ской матема­тике, так и в при­ложе­ниях, пре­имуще­ственно в крип­тографии. Фун­дамен­таль­ным отли­чием функции $10n$ от всех встре­чавшихся нам ранее явля­ется тот факт, что она поли­номи­аль­ная (т. е. имеет вид $C\cdot n^d$ для неко­то­рых $C$, $d>0$) , а не экс­по­ненци­аль­ная. В современ­ной тео­рии слож­но­сти алго­ритмы с такой оцен­кой слож­но­сти (в наи­худ­шем слу­чае) назы­ваются поли­номи­аль­ными, а класс всех задач, кото­рые допус­кают хотя бы один поли­номи­аль­ный алго­ритм, имеет пред­наме­ренно лако­нич­ное назва­ние «P». В этих терми­нах алго­ритм Евклида уста­нав­ли­вает, что задача нахож­де­ния наи­большего общего дели­теля двух чисел лежит в классе P. Класс P обычно отож­деств­ля­ется с клас­сом всех задач, обла­дающих эффек­тив­ным реше­нием в прак­ти­че­ском смысле этого слова. Под­черк­нём, что речь идёт о матема­ти­че­ской абстракции, не пре­тен­дующей (и никогда не пре­тен­до­вавшей) на абсо­лютно точ­ное опи­са­ние реаль­но­сти. Класс P также крайне удо­бен с матема­ти­че­ской точки зре­ния, и это выте­кает из того нехит­рого заме­ча­ния, что при пере­множе­нии двух поли­номов или под­ста­новке одного поли­нома в дру­гой всё равно полу­чится поли­ном. Скажем, при ана­лизе наших преды­дущих алго­ритмов мы писали « $f(n)≈$ » чтобы раз­ли­чать число «попыток» (или ите­раций) и число «элемен­тар­ных опе­раций». Однако все арифме­ти­че­ские действия заве­домо выпол­нимы за поли­номи­аль­ное время (смотри ⁠ «Быст­рая арифме­тика» ), поэтому при иссле­до­ва­нии при­над­леж­но­сти классу P этой раз­ницей можно пре­не­бречь и сосре­до­то­читься на том, что на самом деле важно, т. е. на числе ите­раций. Такие ситу­ации встре­чаются сплошь и рядом. Ещё одним выраже­нием этой заме­ча­тель­ной инва­ри­ант­но­сти явля­ется то обсто­я­тельство, что класс P не зави­сит от выбора вычис­ли­тель­ной модели. У исполь­зующих C++ и Basic (и даже предпо­чи­тающих FORTRAN или, совсем по клас­сике, машины Тью­ринга) класс P один на всех. Предпо­ложе­ние о том, что так будет все­гда, для любого разум­ного вычис­ли­тель­ного устройства, известно, как расши­рен­ный тезис Тью­ринга—Чёрча. Поли­номи­аль­ные алго­ритмы (во многих слу­чаях весьма нетри­ви­аль­ные) суще­ствуют для многих есте­ствен­ных задач. Элемен­тар­ные арифме­ти­че­ские опе­рации в этой связи уже упоми­на­лись ранее; с их более тон­кой гра­дацией внутри класса P можно позна­комиться в ста­тье ⁠ «Быст­рая арифме­тика» . Алго­ритм Евклида даёт поли­номи­аль­ный алго­ритм для нахож­де­ния наи­большего общего дели­теля двух чисел (кстати, как насчёт наименьшего общего крат­ного?). «Исклю­чи­тельно пло­хие» при­меры для сим­плекс-метода озна­чает: при­меры, на кото­рых он рабо­тает экс­по­ненци­аль­ное время. Пер­вый по-насто­ящему поли­номи­аль­ный алго­ритм для линей­ного программи­ро­ва­ния был впер­вые построен совет­ским матема­ти­ком Л. Хачи­я­ном в 1979 году. Пере­ли­стаем насто­ящий сбор­ник. Многие важ­ные задачи для транспорт­ных пото­ков ⁠ «Матема­тика транспорт­ных пото­ков» допус­кают поли­номи­аль­ные алго­ритмы. Алго­ритмы, свя­зан­ные с Интер­не­том ⁠ «Матема­тика интер­нета» являются алго­ритмами лишь в широ­ком смысле, так как сами задачи по своей сути динами­че­ские и рас­пре­де­лён­ные. О них мы пого­во­рим немного позже, пока лишь отме­тим, что поли­номи­аль­ность здесь явля­ется тре­бо­ва­нием заве­домо необ­хо­димым, но никак не доста­точ­ным. Имеющие дело с «большими дан­ными» (big data) обычно наста­и­вают на линей­ных алго­ритмах, т. е. таких, для кото­рых $f(n)\leq Cn$. Все алго­ритмы, исполь­зу­емые в крип­тографии ⁠ «О при­ме­не­ниях матема­тики в крип­тографии» — поли­номи­аль­ные. Это, впро­чем, довольно ред­кий при­мер, бази­рующейся одно­временно как на суще­ство­ва­нии эффек­тив­ных алго­ритмов (для леги­тим­ного поль­зо­ва­теля), так и на предпо­ложе­нии о несуще­ство­ва­нии тако­вых (в слу­чае про­тив­ника). Алго­ритмы, исполь­зу­емые для сжа­тия информации, также являются поли­номи­аль­ными. Борьба идёт за улучше­ние ско­ро­сти коди­ро­ва­ния и деко­ди­ро­ва­ния внутри класса P — как и в слу­чае «больших дан­ных», раз­ница между линей­ными и, скажем, квад­ра­тич­ными алго­ритмами ока­зы­ва­ется весьма ощу­тимой. Про­стой алго­ритм для суще­ство­ва­ния эйле­рова цикла из ста­тьи ⁠ «От прогу­лок по Кёнигсбергу до рекон­струкции генома» — поли­номи­аль­ный. Про пар­ную задачу нахож­де­ния гамильто­нова цикла мы пого­во­рим чуть позже. ⁠ «Игру в „15» можно легко обобщить до «игры в „ $n^21$ “» для про­из­воль­ного нату­раль­ного $n$. Суще­ствует (ско­рее всего — строго это утвер­жде­ние автор не про­ве­рял!) поли­номи­аль­ный отно­си­тельно $n$ алго­ритм, поз­во­ляющий для двух чёт­ных позиций ука­зать путь, пере­во­дящий одну в другую. Кстати, эта задача легко сво­дится (в нашем смысле) к сво­ему част­ному слу­чаю, когда одна из позиций явля­ется пол­но­стью упо­ря­до­чен­ной; может ли чита­тель понять, как именно? Ещё одна задача, кото­рая занимала матема­ти­ков на про­тяже­нии тыся­че­ле­тий — это задача опре­де­ле­ния про­стоты числа. Хотя «почти поли­номи­аль­ные» алго­ритмы (скажем, веро­ят­ност­ные алго­ритмы, кото­рым раз­реша­ется под­бра­сы­вать монетку и оши­биться в ответе с малой веро­ят­но­стью) были известны довольно давно, поли­номи­аль­ный алго­ритм в строгом смысле этого слова был построен лишь в 2002 году. Это открытие вызвало огром­ный резо­нанс как среди матема­ти­че­ского сообще­ства, так и за его пре­де­лами. По‐ви­димому, у ряда чита­те­лей в этот момент должно воз­ник­нуть лёг­кое недо­уме­ние: а в чём соб­ственно раз­ница между тести­ро­ва­нием про­стоты и раз­ложе­нием на про­стые множи­тели? Не одно ли это и то же? Ока­зы­ва­ется, что нет, и в этом про­яв­ля­ется суще­ствен­ное и довольно тон­кое раз­ли­чие между кон­струк­тив­ными дока­за­тельствами и чистыми дока­за­тельствами суще­ство­ва­ния. Скажем, многие из «почти поли­номи­аль­ных» алго­ритмов (с окон­ча­тель­ным алго­ритмом тести­ро­ва­ния про­стоты ситу­ация чуть слож­нее, но принцип тот же) в каче­стве дока­за­тельства того, что число $m$ состав­ное, выда­дут контрпри­мер к малой тео­реме Ферма, т. е. такое $a$, что $a^\neq 1$ в арифме­тике по модулю $m$. Можно ли из этого дока­за­тельства извлечь фак­ти­че­ское раз­ложе­ние $m$ на про­стые множи­тели? Ответ на этот вопрос неиз­ве­стен, положи­тель­ный ответ в виде поли­номи­аль­ного алго­ритма при­вёл бы к весьма ощу­тимым изме­не­ниям в современ­ной циви­ли­за­ции, во многом осно­ван­ной на вере в то, что крип­тографи­че­ские системы типа RSA являются устой­чи­выми. Давайте и мы попро­буем наши скром­ные силы в задаче о раз­ложе­нии на про­стые множи­тели. Как мы уже отме­чали (тре­тий алго­ритм), задача нахож­де­ния НОД двух чисел сво­дится к задаче фак­то­ри­за­ции (раз­ложе­ния на про­стые множи­тели), а алго­ритм Евклида делает это све­де­ние ненуж­ным с прак­ти­че­ской точки зре­ния. Матема­тика, однако, раз­ви­ва­ется по своим соб­ствен­ным зако­нам, и тот факт, что какие-то под­ходы или результаты ока­зы­ваются «уста­ревшими» (учи­ты­вая почтен­ный воз­раст алго­ритма Евклида, дан­ное слово здесь, конечно, весьма условно) совершенно не озна­чает, что заложен­ные в них идеи также ока­зы­ваются бес­по­лез­ными. В дан­ном слу­чае есте­ственно попытаться поступить нао­бо­рот и исполь­зо­вать алго­ритм Евклида для того, чтобы рас­кла­ды­вать числа на множи­тели. Ведь для того, чтобы отыс­кать нетри­ви­аль­ный дели­тель состав­ного числа $m$ (кстати, понятно ли, почему задача пол­ной фак­то­ри­за­ции сво­дится к этой?), доста­точно «всего лишь» разыс­кать такое $n$, для кото­рого $1<\mbox(m,n)кван­то­вого алго­ритма для фак­то­ри­за­ции чисел, при­думан­ного аме­ри­кан­ским матема­ти­ком П. Шором в 1995 году. На послед­нем результате стоит оста­но­виться подроб­нее, так как он дал мощ­ный тол­чок к раз­ви­тию огром­ной современ­ной обла­сти, назы­ва­емой кван­то­выми вычис­ле­ни­ями, в кото­рой бок о бок тру­дятся матема­тики, спе­ци­а­ли­сты в обла­сти тео­ре­ти­че­ской информа­тики и физики. Ника­кого под­воха здесь нет: компью­тер, кото­рый в состо­я­нии исполь­зо­вать законы кван­то­вой меха­ники, в самом деле может раз­лагать $n$ ‐раз­ряд­ные числа на про­стые множи­тели за время, чуть большее $Cn^2$. Кстати, сам алго­ритм исполь­зует весьма кра­си­вую и неожи­дан­ную матема­тику: при­ме­не­ние в самом конце алго­ритма Евклида ока­зы­ва­ется лишь вер­хуш­кой айс­берга. Внима­тель­ный чита­тель, видимо, в этот момент должен слегка уди­виться: выше упоми­на­лось, что класс P не зави­сит от выбора вычис­ли­тель­ной модели, и вдруг мы предъяв­ляем устройство, пусть даже пока и гипо­те­ти­че­ское, кото­рое вдруг ока­зы­ва­ется в состо­я­нии делать такие заме­ча­тель­ные вещи. Ника­кого под­воха здесь нет также. Именно, мир, в кото­ром мы живём, устроен одним из трёх сле­дующих спо­со­бов: 1) постро­е­ние прак­тич­ного кван­то­вого компью­тера невозможно (и, тем самым, эта модель при­рав­ни­ва­ется к «нера­зум­ным»); 2) расши­рен­ный тезис Тью­ринга—Чёрча неве­рен (и, видимо, возможны откло­не­ния от него, исполь­зующие и другие физи­че­ские или био­логи­че­ские законы); 3) для фак­то­ри­за­ции чисел суще­ствует клас­си­че­ский поли­номи­аль­ный алго­ритм (со всеми выте­кающими отсюда послед­стви­ями). Мы про­сто пока не знаем, как именно он устроен. К этому можно лишь доба­вить, что в мире № 1 невозмож­ность постро­е­ния кван­то­вого компью­тера должна, ско­рее всего, опре­де­ляться пока непо­нят­ными фун­дамен­таль­ными, а не тех­но­логи­че­скими препят­стви­ями: как пока­зы­вает опыт чело­ве­че­ского раз­ви­тия, при нали­чии доста­точ­ной воли (а в постро­е­ние кван­то­вого компью­тера вкла­ды­ваются весьма зна­чи­тель­ные сред­ства во многих раз­ви­тых стра­нах), послед­ние рано или поздно пре­одо­ле­ваются. Так что попу­ляр­ный тезис о заве­домой бес­про­иг­рыш­но­сти этой дея­тель­но­сти (на выходе — или кван­то­вый компью­тер или новые физи­че­ские законы, объяс­няющие невозмож­ность его постро­е­ния) по край­ней мере не лишён неко­то­рых осно­ва­ний. Теперь мы немного пого­во­рим о про­блеме ниж­них оце­нок в тео­рии слож­но­сти вычис­ле­ний, а именно, дока­за­тельстве того, что для кон­крет­ных инте­рес­ных задач любой алго­ритм должен иметь слож­ность $f(n)\geq \varepsilon\cdot b(n)$, где $b(n)$ — неко­то­рая фик­си­ро­ван­ная функция. Верши­ной здесь было бы дока­за­тельство того, что какая-нибудь инте­рес­ная задача не при­над­лежит классу P, т. е. не допус­кает ника­кого алго­ритма с верх­ней оцен­кой слож­но­сти $f(n)\leq Cn^k$ (о пер­спек­тив­ных кан­ди­да­тах мы пого­во­рим позже). Возьмём для при­мера задачу фак­то­ри­за­ции. Крас­ной нитью через наше изложе­ние про­хо­дил тезис о том, что задача фак­то­ри­за­ции чисел не лежит в P, при­чём, в отли­чие от тезиса Тью­ринга—Чёрча, это матема­ти­че­ское предпо­ложе­ние. Коли­че­ство чело­веко-часов, потра­чен­ное на его опро­верже­ние (в том числе и часов, отно­сящихся к наи­бо­лее силь­ным спе­ци­а­ли­стам по тео­рии чисел и алго­ритмам) не под­да­ётся ника­кому исчис­ле­нию. Озна­чает ли это, что нам сле­дует про­сто при­нять его за некий физи­че­ский закон и заняться чем‐то ещё? Конечно же, для любого рабо­тающего матема­тика этот вопрос чисто рито­ри­че­ский и может в лучшем слу­чае вызвать лёг­кую улыбку. Тот факт, что на про­тяже­нии весьма долгого времени никто не был в состо­я­нии предъявить нетри­ви­аль­ное реше­ние урав­не­ния $x^n+y^n=z^n$ или трёхмер­ное много­об­ра­зие с «дикими» свойствами (контрпри­мер к гипо­тезе Пуан­каре), матема­ти­ков в поиске дока­за­тельства соот­вет­ствующих утвер­жде­ний только раз­за­до­ри­вал, и совсем не напрасно. В процессе их реше­ния с кульми­нацией, наступившей в рабо­тах Э. Уайлса и Г. Перельмана, соот­вет­ственно, были созданы целые строй­ные тео­рии, занявшие своё достой­ное место в зда­нии современ­ной матема­тики. Точно так же обстоит дело и с про­блемой ниж­них оце­нок слож­но­сти, с той раз­ницей, что она в насто­ящий момент оста­ётся широко открытой, хотя ряд обна­дёжи­вающих результа­тов и был полу­чен в 80‐е и 90‐е годы XX века. По‐ви­димому, для её пол­ного реше­ния потре­буются неко­то­рые, пока неиз­вест­ные идеи (впро­чем, по срав­не­нию, скажем, с тео­ремой Ферма или гипо­те­зой Пуан­каре, про­блема ниж­них оце­нок слож­но­сти нахо­дится в мла­ден­че­ском воз­расте). При­чину такого положе­ния дел понять легко. Любое дока­за­тельство несуще­ство­ва­ния эффек­тив­ного (скажем, поли­номи­аль­ного) алго­ритма для дан­ной задачи должно непременно учи­ты­вать не только все уже суще­ствующие идеи для постро­е­ния такого алго­ритма, но также и все потенци­аль­ные идеи, кото­рые могут появиться в будущем: в этом, соб­ственно, и состоит смысл тео­рии слож­но­сти. Этот класс идей весьма широк, и большин­ство извест­ных част­ных результа­тов по про­блеме ниж­них оце­нок полу­чаются как раз путём его суже­ния. В заклю­че­ние нашего крат­кого очерка сле­дует рас­ска­зать про NP-пол­ноту: это именно тот раз­дел, в кото­ром успехи тео­рии слож­но­сти вычис­ле­ний уже ока­зы­ваются весьма впе­чат­ляющими. Основы тео­рии NP-пол­ноты были заложены в рабо­тах аме­ри­кан­ских матема­ти­ков C. Кука, Р. Карпа и совет­ского матема­тика Л. Левина в начале 70‐х годов. Давайте ещё раз взгля­нем на задачу нахож­де­ния нетри­ви­аль­ного дели­теля состав­ного числа и срав­ним её с двумя другими зада­чами из дан­ного сбор­ника: нахож­де­ния гамильто­нова цикла ⁠ «От прогу­лок по Кёнигсбергу до рекон­струкции генома» и реше­ния судоку ⁠ «Раз­га­ды­ва­ние судоку» ; послед­нюю, конечно, надо обобщить на слу­чай таб­лицы $n^2\times n^2$. Что между ними всеми общего? На «фило­соф­ском» уровне понятно, что реше­ние всех таких задач раз­би­ва­ется на два совершенно нерав­но­цен­ных этапа: поиск или уга­ды­ва­ние пра­виль­ного ответа и его про­верка. Послед­нюю во всех слу­чаях про­ве­сти легко и можно пору­чить компью­теру или даже школь­нику. Насчёт того, как пра­виль­ный ответ найти, ника­ких общих рецеп­тов у нас нет, а в лучшем слу­чае есть лишь разум­ные советы, иногда назы­ва­емые эври­сти­ками (смотри, напри­мер, ⁠ «Раз­га­ды­ва­ние судоку» ). Хорошо, однако, то, что пра­виль­ный ответ по край­ней мере ока­зы­ва­ется корот­ким или, более матема­ти­че­ски, его бито­вая длина $m$ не пре­вос­хо­дит поли­нома от бито­вой длины записи $n$ самой задачи. Поэтому все­гда име­ется три­ви­аль­ный пере­бор­ный алго­ритм, кото­рый вме­сто орга­ни­зо­ван­ного поиска про­сто пере­би­рает под­ряд все возмож­но­сти, пока не натолк­нётся на нуж­ную. Его слож­ность в наи­худ­шем слу­чае порядка $2^m\sim 2^$. Учи­ты­вая ско­рость роста экс­по­ненци­аль­ной функции, это, конечно, не ахти, но стоит отме­тить, что бывают ситу­ации и намного хуже. Из дан­ного в преды­дущем абзаце опи­са­ния срав­ни­тельно легко скон­стру­и­ро­вать матема­ти­че­ское опре­де­ле­ние: класс задач, в кото­рых про­верка ответа поли­номи­альна, т. е. лежит в классе P. Экви­ва­лент­ное опре­де­ле­ние полу­ча­ется, если в при­ве­дён­ное в начале заметки опи­са­ние машины Тью­ринга доба­вить пункт о её неде­терми­ни­ро­ван­но­сти, т. е. раз­решить машине по сво­ему усмот­ре­нию выби­рать один вари­ант пове­де­ния из списка пред­ложен­ных. Полу­чен­ный таким обра­зом класс задач назы­ва­ется NP, где «N» напоми­нает о неде­терми­ни­ро­ван­но­сти. Большин­ство задач, кото­рые мы обсуж­дали ранее, при­над­лежат этому классу или могут быть легко при­ве­дены к тре­бу­емому виду. Такая широ­кая рас­про­стра­нён­ность, конечно же, не слу­чайна. Она отражает тот факт, что NP явля­ется непло­хой матема­ти­че­ской моде­лью любой орга­ни­зо­ван­ной твор­че­ской дея­тель­но­сти, состо­ящей из соб­ственно твор­че­ского акта поиска реше­ния и (как пра­вило быст­рой и рутин­ной) фазы его про­верки. Учи­ты­вая такое много­об­ра­зие задач в NP, a priori сле­до­вало бы ожи­дать суще­ство­ва­ние внутри этого класса бога­той иерар­хи­че­ской струк­туры, пытающейся сор­ти­ро­вать задачи в соот­вет­ствии с их внут­рен­ней слож­но­стью, предпо­ложе­ний о том, куда именно та или иная задача попа­дает и т. д. Ока­зы­ва­ется, что ничего этого не про­ис­хо­дит. За весьма немногими исклю­че­ни­ями, класс NP фак­ти­че­ски рас­па­да­ется ровно на два больших куска. Пер­вый кусок — это уже извест­ный нам класс P, состо­ящий из всех алго­ритми­че­ских задач, допус­кающих хотя бы один эффек­тив­ный (поли­номи­аль­ный) алго­ритм. Иными сло­вами, это те задачи, в кото­рых пере­бор вари­ан­тов уда­ётся заме­нить эффек­тив­ной проце­ду­рой, что мы, соб­ственно, и наблю­дали на при­мере алго­ритма Евклида (дру­гой хре­сто­ма­тий­ный при­мер — задача про эйле­ров цикл из ста­тьи ⁠ «От прогу­лок по Кёнигсбергу до рекон­струкции генома» ).

На про­ти­вопо­лож­ном полюсе нахо­дятся так назы­ва­емые NP-пол­ные задачи, обла­дающие тем свойством, что к ним поли­номи­ально сво­дится любая другая задача из класса NP. Ока­зы­ва­ется, что и задача раз­га­ды­ва­ния судоку и задача нахож­де­ния гамильто­нова цикла из ста­тьи ⁠ «От прогу­лок по Кёнигсбергу до рекон­струкции генома» и ещё более тысячи (с учё­том всех вари­аций — порядка $10 000$) алго­ритми­че­ских задач из самых раз­ных обла­стей матема­тики, компью­тер­ных наук, есте­ство­зна­ния, био­логии, социо­логии и т. д. NP-полны. Таким обра­зом, любой эффек­тив­ный алго­ритм для раз­га­ды­ва­ния судоку может быть пере­строен в эффек­тив­ный алго­ритм для раз­ложе­ния чисел на про­стые множи­тели, постро­е­ния гамильто­нова цикла и массы других полез­ных вещей. Все такие редукции имеют ярко выражен­ный «моду­ляр­ный харак­тер»: поли­номи­аль­ное све­де­ние, скажем, гамильто­нова цикла к судоку раз­би­ва­ется на несколько срав­ни­тельно корот­ких пере­хо­дов от одной есте­ствен­ной промежу­точ­ной задачи к дру­гой. Все встре­чающи­еся нам по дороге задачи могут также быть зачис­лены в NP-пол­ные. А вот между этими двумя полю­сами нет прак­ти­че­ски ничего. Одна NP-задача, кото­рую мы не умеем клас­сифици­ро­вать — это раз­ложе­ние чисел на про­стые множи­тели; име­ется ещё несколько при­ме­ров такого типа, моти­ви­ро­ван­ных крип­тографи­че­скими предпо­ложе­ни­ями. Все они обла­дают тем свойством, что пра­виль­ный ответ един­стве­нен. При­ме­ром, в кото­ром послед­нее свойство не выпол­ня­ется, служит задача изо­морфизма графов (нари­со­ваны два графа, можно ли их так «наложить» друг на друга, что они совпа­дут) и её раз­но­вид­но­сти. Вот, пожа­луй, и все (или, по край­ней мере, наи­бо­лее важ­ные) есте­ствен­ные задачи, ста­тус кото­рых пока неиз­ве­стен. Так что с уве­рен­но­стью можно ска­зать, что клас­сифи­кация пере­бор­ных задач на про­стые (P) и мак­симально труд­ные (NP-пол­ные) — это один из наи­бо­лее успеш­ных клас­сифи­каци­он­ных про­ек­тов в исто­рии науки. По всем этим при­чи­нам задача о совпа­де­нии клас­сов P и NP (извест­ная также, как про­блема пере­бора) — это одна из цен­траль­ных открытых про­блем современ­ной матема­тики. Большин­ство спе­ци­а­ли­стов верят в то, что $\mbox\neq \mbox$. Но дока­за­тельство этого факта сво­дится к про­блеме ниж­них оце­нок для про­из­вольно выбран­ной NP‐пол­ной задачи, чего матема­тики делать пока не умеют. О попу­ляр­но­сти этой задачи сви­де­тельствует, в част­но­сти внима­ние, про­яв­ля­емое к ней люби­те­лями от матема­тики — по этому кри­те­рию про­блема пере­бора, возможно, уже пре­взошла гипо­тезу Ферма. Однако и про­фес­си­о­налы за пре­де­лами матема­ти­че­ской логики и компью­тер­ных наук, без­условно, отдают ей долж­ное. Про­блема пере­бора — одна из семи задач, за реше­ние кото­рой матема­ти­че­ский инсти­тут Клэя учре­дил пре­стиж­ную премию. Как известно, пока решена только одна из них (гипо­теза Пуан­каре — Г. Перельман); для реше­ния оставшихся, ско­рее всего, также пона­до­бятся новые идеи и под­ходы, о при­роде кото­рых мы в слу­чае про­блемы пере­бора не имеем даже при­бли­зи­тель­ного пред­став­ле­ния.

Допол­не­ния, коммен­та­рии

Уже гово­ри­лось, что между клас­сами P и NP‐пол­ных задач, этими свое­об­раз­ными полю­сами в объеди­няющем классе NP, есть несколько задач, кото­рые пока не клас­сифици­ро­ваны. Про одну из них, задачу изо­морфизма графов, уже после выхода пер­вого изда­ния этой книги в 2015 году венгро-аме­ри­кан­ский матема­тик Л. Бабаи дока­зал фун­дамен­таль­ный результат: для этой задачи суще­ствует «почти поли­номи­аль­ный» алго­ритм, время его работы — $2^\!$. Полу­ча­ется, что задача изо­морфизма графов нахо­дится как минимум неда­леко от класса P.

Классификация алгоритмов по временной сложности

Применение порядковых оценок определения сложности алгоритмов, с одной стороны, и исследование возможностей решения различных задач на современных ЭВМ — с другой позволили по характеристике время решения задачи выделить два класса алгоритмов: полиномиальные и экспоненциальные. К классу полиномиальных алгоритмов относят те из них, для которых функция /(п) при п —> со растет не быстрее, чем некоторый полином (многочлен) от п. Если же указанная функция растет быстрее, алгоритм относят к классу экспоненциальных алгоритмов. Например, алгоритм с функцией /(л) = 100л 3 + п 2 +10 — полиномиальный. Алгоритмы, для которых /(л) = 2″+л 2 , /(л) = е 2 «,

/(л) = л! — экспоненциальные.

В сравнении с экспоненциальными алгоритмами алгоритмы с полиномиальным ростом сложности вычислений характеризи-руются рядом положительных свойств. Во-первых, при увеличении размера задачи л время счета по этим алгоритмам растет значительно медленнее, чем по экспоненциальным, даже в том случае, когда для малых л полиномиальный алгоритм затрачивает больше времени, чем экспоненциальный. Во-вторых, полиномиальные алгоритмы лучше используют технологии производства ЭВМ, направленные на повышение их производительности. Так, если удается увеличить производительность ЭВМ, например, в 10 раз, размер задач, решаемых полиномиальным алгоритмом, увеличивается в 1 20 ’ 65+2 ’ 15,, > = ехр (-20,65 + 2,15л), указывающей на то, что, с одной стороны, она носит экспоненциальный характер, с другой — уже при п= 12 для генерации всех перестановок указанной ЭВМ требуется три минуты. При л =13 для достижения этой цели компьютер должен затратить примерно 23 минуты, а при л= 14 — немногим меньше 3,5 ч. Такое время перебора вариантов в практических условиях не всегда допустимо.

Все множество задач, решаемых полиномиальными алгоритмами, называют классом Р (полиномиальный). Для определения класса задач, решаемых только экспоненциальными алгоритмами, введено понятие недетерминированного алгоритма. Это воображаемый полиномиальный алгоритм, который в каждом состоянии может выполнять как угодно много альтернативных действий одновременно. Чтобы проиллюстрировать работу такого алгоритма, рассмотрим задачу путешествующего продавца (коммивояжера). Этот продавец имеет товарную базу в одном из городов его региона продаж, например в городе 1, и должен объехать еще три города для того, чтобы продать свои товары и потом вернуться в исходный город 1. Различные порядки объезда городов, скажем, 1—2—3—4 и 1—3—2—4, требуют различного расхода бензина и, следовательно, имеют различную стоимость, что обусловлено различным профилем автомобильных дорог. Продавец должен выбрать такой порядок объезда городов (маршрут), который обеспечит наименьшую его стоимость.

Таким образом, поскольку каждый маршрут объезда городов — это перестановка их номеров или названий, всегда начинающаяся с города 1, в этой задаче требуется найти все остальные перестановки на множестве трех номеров городов 2, 3, 4, оценить их стоимость и выбрать наилучшую перестановку.

Все перестановки, а их 3! = 6, легко построить, используя корневое дерево перебора. В корневой вершине дерева указывается номер исходного города. В вершинах первого яруса отмечаются части маршрутов, которые ведут из города 1 в остальные города 2, 3, 4. Вершины второго яруса указывают части маршрутов, которые можно проложить из городов первого яруса. В вершинах последнего, третьего яруса указаны полные маршруты объезда городов, т. е. полные перестановки. Дерево изображено на рис. 1.2.

Рис. 1.2. Дерево маршрутов в задаче коммивояжера

для четырех городов

Согласно этому дереву детерминированный алгоритм формировал бы и оценивал маршруты последовательно. Например, он бы последовательно строил самую левую ветвь, т. е. сформировал бы маршрут 1—2—3—4 и оценил его. Затем вернулся бы в вершину М_|2 и достроил вершины М|₂₄, М|242, т. е. построил бы маршрут 1—2—4—3 и оценил его. Потом вернулся бы в корневую вершину дерева и построил маршрут 1—3—2—4 и т. д. Всего бы он сформировал шесть ветвей, возвращаясь при этом на необходимый ярус дерева. По определению недетерминированный алгоритм, находясь в состоянии М,, одновременно сформирует три вершины дерева М₁₂, М₁₃, М_|4. Находясь в этом состоянии, т. е. на ярусе 1, он одновременно сформирует шесть вершин М |2з, М₁₂₄, М₁₃₂ М₁₃₄, М₁₄₂, М₁₄₃. Находясь затем на 2-м ярусе, недетерминированный алгоритм одновременно сформирует вершины последнего яруса дерева маршрутов. Таким образом, это дерево он мог бы построить за три последовательных шага, так как будто бы строилась одна ветвь, т. е. за полиномиальное время.

В какой-то мере действия недетерминированного алгоритма напоминают работу многопроцессорной ЭВМ с бесконечным числом асинхронно включающихся в работу процессов. Однако никакое физическое устройство пока не может быть построено по этому принципу. Например, только в случае двоичного дерева высотой п на последнем его ярусе будет образовано 2″ листьев, что при п = 30 потребует больше миллиарда процессоров для их обработки.

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

Другое толкование понятия «недетерминированный полиномиальный» несколько иное. Оно вытекает из того, что недетерминированность алгоритма подразумевает неопределенность количества шагов предполагаемого двухэтапного способа решения задачи. На первом этапе этого способа за полиномиальное время находится возможное ее решение. На втором этапе тоже за полиномиальное время проверяется, действительно ли это решение рассматриваемой задачи. Хотя каждый из этапов требует полиномиального времени решения, число обращений к ним может оказаться экспоненциальным. Такая задача попадает в класс А!Р, так как для поиска ее необходимого решения требуется просматривать огромное количество побочных решений и нет алгоритма интенсивного отбрасывания заведомо не нужных из них.

Хотя классы задач Р и Л^Р являются различными, любая задача из Р принадлежит множеству ЫР. Это обусловлено тем, что любая задача из класса Р, решаемая детерминированным алгоритмом, может быть представлена как описанный двухэтапный процесс решения: вначале находится любое решение, затем проверка, действительно ли это решение. Причем PczNP, так как для класса А ! Р неизвестны детерминированные полиномиальные алгоритмы. Однако это не означает, что такого алгоритма не существует. Пока этот тезис не удалось доказать. Поэтому проблема, равны ли классы Р и NP, является открытой.

В классе задач Л^Р существует подмножество задач, которые принято называть АТ’-полными. Эти задачи обладают особой сложностью решения и отличаются от остальных задач класса А Г Р тем, что если удастся найти полиномиальный алгоритм решения какой-либо из них, то это будет означать, что все задачи из А‘Р могут быть решены полиномиальными алгоритмами.

Выделение класса А^Р-полных задач основано на преобразовании одной задачи в другую.

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

При отнесении некоторой задачи А к классу АР’-полных задач поступают наоборот. К этой задаче А сводят (преобразовывают в нее) некоторую АР^-полную задачу. Тем самым подтверждают, что выбранная АР’-полная задача выражается в терминах А, т. е. А также принадлежит к классу АР’-полных задач.

Таким образом, класс АР>-полных задач — это класс задач из А!Р, которые преобразуются одна в другую. Именно на это опирается утверждение, что если будет найден полиномиальный алгоритм для некоторой АР’-полной задачи, то все другие АР’-полные задачи также могут быть решены с помощью своего полиномиального алгоритма.

Понятия Р и АР’-полных задач позволяют проводить анализ эффективной разрешимости новых задач до составления решающих их алгоритмов. Это, во-первых, существенно экономит время, затрачиваемое на разработку подходящих алгоритмов решения новых задач, во-вторых, заставляет сосредоточить усилия на поиске приближенных алгоритмов их решения, во многих случаях более пригодных для практических применений.

К настоящему времени большинство задач дискретной математики по показателю «сложность алгоритмов решения» классифицировано, т. е. отнесено к классам Р и А ] Р. Кроме задач на поиск наибольшего (наименьшего) значения функций (функционалов), в класс АР*включены так называемые задачи распознавания, решением которых является ответ «да—нет». Эти задачи не труднее в отношении решения, чем экстремальные задачи, однако во многих случаях они оказались более удобными для целей классификации. Особое место среди этих задач занимает задача из раздела математической логики о выполнимости булевой формулы. Обычно она представляется в конъюнктивной нормальной форме (КНФ). Например, как (х, V х₂ V х₃) л (х, V х₂ V х₄) л (х₃ х₄) л х,,

где булевы переменные х,, х₂, х₃, х₄ называются литералами, а дизъюнкции х,, х₂, х₃, х₄ или их отрицания — дизъюнктами.

Булева формула считается выполнимой, если существует некоторый набор литералов такой, что она получает значение «истина». Если же такого набора литералов не существует, формула является невыполнимой. Задача о выполнимости булевой формулы состоит в том, чтобы выяснить, есть ли некоторый набор литералов, для которых значение булевой формулы истинно.

Очевидное решение этой задачи — перебор 2″ наборов литералов, построение для каждого набора таблицы истинности функций и выяснение по ней, истинна ли булева формула. Такой алгоритм имеет сложность 0(2″), т. е. он экспоненциальный и, таким образом, неэффективный. Других алгоритмов решения этой задачи нет. Наоборот, доказано, что эта задача принадлежит к классу ./УР-полных задач [4, 5].

Доказательство УУР-полноты задачи о выполнимости булевой формулы в свою очередь послужило основанием не только для классификации других задач, а в большей мере для развития самой логики доказательства УУР-полноты. Она состоит в следующем. Для того чтобы доказать, что некоторая задача УУР-полна, необходимо логически обосновать два положения:

• 1) задача входит в класс ТУР;
• 2) задача также трудна по решению, как и известные УУР-полные задачи этого класса.

Весьма часто и успешно для обоснования первого положения используется понятие недетерминированного алгоритма. Если удается показать, что рассматриваемая задача может быть решена недетерминированным алгоритмом за полиномиальное время, то она автоматически входит в класс /УД-задач. Доказательство УУР-трудности задачи осуществляется путем преобразования (полиномиального сведения) некоторой УУР-полной задачи в рассматриваемую задачу. Иными словами, необходимо подобрать наиболее подходящую УУР-полную задачу и представить ее в терминах той задачи, которая нуждается в доказательстве ее ЛТ’-полноты. Подробно с логикой доказательства можно познакомиться по книге [6].

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

§ 5. NP -полные и NP -трудные задачи

Рассмотрим сводимость задач. Хотя сведение одних задач к другим является традиционной математической деятельностью, оно до работ С. Кука не было подвержено самостоятельному исследованию. Именно С. Куку принадлежит честь выделения этого понятия как центрального в теории полиномиальной сводимости.

Говорят, что задача Z 1 сводится к задаче Z 2 если метод решения задачи Z 2 можно преобразовать в метод решения задачи Z 1 . Сводимость называется полиномиальной если указанное преобразование можно осуществить за полиномиальное время.

Если одновременно задача Z 1 полиномиально сводится к задаче Z 2 и Z 2 полиномиально сводится к задаче Z 1 , то задачи Z 1 и Z 2 полиномиально эквивалентны.

Задача называется NP — трудной если каждая задача из NP полиномиально сводится к ней.

NP- трудная задача имеет тот смысл, что эта задача не проще, чем «самая трудная в NP ».

В классе NP выделяются NP -полные задачи. Задача называется NP — полной , если она входит в NP и каждая задача из NP полиномиально сводится к ней (т.е. является NP -трудной). NP -полные задачи понимаются как самые трудные задачи из класса NP .

Класс NP- полных задач обладает следующими свойствами.

1. Никакую NP -полную задачу нельзя решить никаким известным полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестящих исследователей.

2. Если бы удалось построить полиномиальный алгоритм для какой-нибудь NP -полной задачи, то это бы означало

полиномиальную разрешимость каждой NP -полной задачи. Основываясь на этих двух свойствах, многие высказывают гипотезу, что P ≠ NP. Практическое значение понятия NP -полной задачи лежит именно в широко распространенном мнении, что такие задачи по существу труднорешаемы. Следовательно, при их решении в худшем случае потребуется экспоненциальное количество времени и не будет возможности решить на практике такие задачи, за исключением очень малого числа индивидуальных задач.

Первой задачей, для которой было доказано, что она является NP — полной, была проблема о выполнимости (см. задачу 1 в § 4), именно, имеет место следующая теорема.

Теорема 7.1 (теорема Кука). Задача выяснения выполнимости формулы логики высказываний, представленной в к.н.ф., является NP — полной.

Все приведённые ранее примеры NP- задач (задачи 1-12) являются NP — полными задачами. Список NP -полных задач в настоящее время содержит несколько сотен задач и продолжает пополняться. Многие вновь установленные NP -полные задачи печатаются в журнале Journal of Algorithms. В действительности о большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либо NP — полнота, что является ещё одним подтверждением гипотезы P ≠ NP .

§ 6. Класс Е

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

Кроме этого определения существует и второе определение: алгоритм имеет экспоненциальную временную сложность если его временная сложность имеет порядок не меньше, чем сa n , где с >0, a (a > 1) — постоянные. Иначе, временная сложность f(n) является экспоненциальной, если существуют постоянные с >0, a >1 , что

для всех, кроме конечного числа значений n .

При первом определении, например задача, имеющая сложность порядка 0(n log 2 n ) ( 0(n log 2 n ) = 0( 2 (log 2 n ) 2 ) ) будет отнесена к задаче с экспоненциальной временной сложностью, а по второму определению – нет.

Отметим, что функция n log 2 n хотя и растет быстрее любого полинома, но растёт медленнее, чем, например 2 n .

Большинство экспоненциальных алгоритмов – это просто варианты полного перебора. Экспоненциальные алгоритмы не считаются «хорошими», в отличие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного

множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа.

Некоторые экспоненциальные алгоритмы весьма хорошо зарекомендовали себя на практике. Дело в том, что временная сложность определяется для худшего случая, а многие задачи могут быть не так плохи.

Для решения задачи линейного программирования существует так называемый симплекс-метод (алгоритм), который хотя и экспоненциален в худшем случае – уверено работает на практике для задач достаточно большого размера. Отметим, что для решения задачи линейного программирования Хачиян Л. Г. в 1979 г. предложил алгоритм эллипсоидов, который имеет полиномиальную временную сложность.

Метод ветвей и границ успешно решает задачу о рюкзаке, хотя этот алгоритм имеет экспоненциальную временную сложность.

Примеров экспоненциальных алгоритмов успешно используемых на практике мало. Более того даже для полиномиальных алгоритмов представляют практический интерес алгоритмы сложность которых имеет порядок n 2 или n 3 . Ясно, что алгоритмы со сложностью порядка n 100 вряд ли будут практически используемы.

Интересно, что экспоненциальный алгоритм может оказаться при малом размере задачи более быстрым, чем полиномиальный, однако с ростом размера задачи полиномиальный становится более быстрым.

Экспоненциальная сложность задачи имеет следующие аспекты: -для отыскания решения требуется экспоненциальное время;

-искомое решение может быть настолько велико, что не может быть представлено выражением, длина которого была бы ограничена полиномом от длины входа.

Вторая ситуация возникает, например, если в задаче коммивояжера требуется найти все маршруты длины, не превосходящей заданной величины L . Может оказаться, что имеется экспоненциальное число маршрутов длины не превосходящей L .

§ 7. Ёмкостная (ленточная) сложность алгоритма

Ёмкостная или ленточная сложность алгоритма характеризует необходимую для вычисления память для хранения исходных данных, промежуточных результатов и окончательного результата. При применении машины Тьюринга как модели вычислений, ёмкостная сложность оценивается длиной части ленты используемой для записи исходных данных и вычислений.

Пусть машина Тьюринга вычисляет значение функции f.

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

Активной зоной при работе машины Тьюринга на числе n называется объединение всех активных зон за время вычисления.

Определим S f (x) как длину активной зоны при работе машины Т на числе х , если f(x) определено. В противном случае значение S f (x) будем считать неопределённым. Функцию S f (x) назовём ленточной сложностью .

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

Для задач вводятся понятия задач с полиномиальной потребной памятью, с NP -потребной памятью и т.д.

Имеет место следующая теорема:

Теорема 7.2. Для ленточной (ёмкостной) характеристики сложности вычисления функции f имеет место оценка

S f (x) ≤ x+1+ t f (x),

где t f (x) -временная сложность вычисления f(x) .

Доказательство . В начальный момент на ленте машины Тьюринга записано число х (в унарной системе), следовательно, занято х+1 клеток ленты. На каждом такте (шаге) активной становится не более одной новой клетки, поэтому получим указанную оценку для S f (x) .

Эта теорема показывает, что если известна временная сложность, то можно оценить сверху ленточную сложность.

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

§ 8. Вопросы и темы для самопроверки

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

2. Размер исходных данных задачи для случаев, когда входом является число, матрица, граф.

3. Временная сложность алгоритма. Временная сложность задачи.

4. Временная сложность алгоритма в наихудшем случае, временная сложность алгоритма в среднем.

5. Может ли, что для решения одной и той же задачи существовать алгоритмы разной сложности? Если да, то какова сложность задачи?

6. Полиномиальная сложность алгоритма, задачи.

7. Классификация задач по сложности.

8. Класс Р , примеры задач из этого класса.

10. Недетерминированная машина Тьюринга, её отличие от детерминированной машины Тьюринга.

Похожие публикации:

1. Google ngram viewer что это
2. Seed раунд что это
3. Валидные реквизиты что это
4. Как добавить сетевой мост enp0s3 порт