Классы сложности и нотация большого O - это не одно и то же. Обозначение Big-O - это просто обозначение для передачи асимптотического c поведения функции; то есть O (f (n)) - это набор всех функций, которые ограничены сверху значением c* f (n) для всех n> N, где c и N - универсальные константы. Итак, в вашем примере мы бы сказали, что n ^ 2 + n находится в O (n ^ 2), потому что для всех n> = 1, n ^ 2 + n <2n ^ 2. </p>
Сложность классы, с другой стороны, являются классами языков , которые мы можем рассматривать как «проблемы решения (например, решить, имеет ли какой-либо объект X заданное свойство). Классы сложности описывают, сколько вычислительной мощности требуется для алгоритма для решения данной проблемы принятия решения. Например, предположим, что мы хотим решить, отсортирован ли массив из n чисел в порядке возрастания. Поскольку мы можем сделать это, просто сканируя элементы по одному и проверяя, нет ли уменьшение, требуется n шагов для решения проблемы решения. Таким образом, эта проблема принятия решения находится в классе P, который содержит все языки с алгоритмами полиномиального времени. Обратите внимание, что это свойство задачи, а не заданная функция. Вы также можете решить, сортируется ли список, перечислив все списки по n элементам и проверив, что входные данные совпадают с любым, но это было бы действительно неэффективно. Классы сложности - d определяется наличием достаточного алгоритма для решения проблемы решения.