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

[Organon]

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

Если, конечно, щелкнут на кат

В общем случае можно считать, что для двух функций f(x) и g(x) выполняется соотношение:
g(x)=O(f(x)) (читается "жэ от икс есть О-большое от эф от икс") в некоторой точке х₀, если существует такая положительная константа С, что для любых значений х из окрестности этой точки
|g(x)| ≤ С•|f(x)|
иными словами, отношение |g(x)|/|f(x)| ограничено сверху некоторой константой.
Или, что еще проще, хотя и несколько фривольно, это величины одного порядка.

Для о-малого (хоть мы его больше касаться и не будем) соотношение иное:
g(x)=о(f(x)) в некоторой точке х₀, если отношение абсолютных величин этих функций стремится к нулю в окрестности этой точки.
|g(x)|/|f(x)| → 0
Например, в окрестности нуля верно, что х²=o(x), и вообще хⁿ=o(x^n-1)
Здесь на самом деле нас может ждать множество подвохов, потому что о-малое при таком определении вещь очень неоднозначная.
Например, в окрестности нуля будет выполняться много много равенств:
х²=o(x)
х³=o(x)
х⁴=o(x)
...
и т.д.
Поэтому мы и не будем трогать о-малые.
Нам и О-больших хватит за глаза.

Что же такое О-нотация применительно к сложности алгоритмов?

Если говорят, например, что сложность данного класса алгоритмов O(N), это означает, что существует некоторая константа C, единая для всех алгоритмов этого класса, такая, что количество элементарных шагов, сделанных алгоритмом, не будет превосходить C•N операций, где N - объем начальных данных задачи.

Для алгоритмов класса O(N) для каждого входного элемента выполняется только одно действие. (На самом деле, может быть, конечно, не одно, а два, три, и т.д., но главное не больше С•N, где С — константа).
Для программистов (для меня по крайней мере) неформально это легко представить следующим образом: у нас может быть сколько угодно (но конечное число) одномерных циклов, пробегающих весь набор входных данных, идущих друг за другом (идущих циклов, а не данных), но вложенных циклов быть не может.
Плюс, естественно, может быть некоторый набор шагов до, после и между циклами.
Для алгоритмов класса O(N²) каждый входной элемент обрабатывается (или проходится) С•N² раз. Это означает (для наглядности, только как одну из возможностей) наличие вложенных (двойных) циклов.
Для алгоритмов класса O(N³) — С•N³. Здесь уже цикл-в-цикле-в-цикле.
И т.д.
Все эти классы являются подклассами общего класса: O(N^x), где х - любое (целое) число.
Это класс алгоритмов, работающих с полиномиальной скоростью.
Он и называется Р-классом.

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