Сложность задачи определяется через сложность наилучшего алгоритма, известного для ее решения.
Быстрыми алгоритмами являются линейные, которые обладают сложностью порядка n, и называются алгоритмами порядка 0(n), где n – размерность входного данного.
К линейным алгоритмам относятся:
алгоритм нахождения суммы для типичных чисел, состоящих из n1 и n2 цифр. Его сложность 0(n1)+n2.
Есть более быстрые алгоритмы, чем линейные. Например, алгоритм двоичного поиска в линейном упорядоченном массиве, его сложность 0(log2n), где n – длинна упорядоченного массива.
Другие хорошо известные алгоритмы: деление, извлечение квадр. корня – решение систем линейных уравнений попадают в более общий класс полиномиальных алгоритмов.
Полиномиальные алгоритмы – алгоритмы, принадлежащие классу Р, эти алгоритмы имеют полиномиальную временную сложность и в общем виде их сложность записывается 0(nк), где к из Z, k>0.
Алгоритмы для которых не существует такой временной оценки – экспоненциальные. Задача, считается трудно решаемой. Если для нее не существует решающего эту задачу полиномиального алгоритма.
Отметим, что экспоненциальным алгоритмом при небольших значениях n может быть более быстрым, чем полиномиальным, однако различие между двумя этими типами задач очень велико и всегда проявляется при больших значениях n.
Класс Р: Задачу называем «хорошей» если для нее существует полиномиальный алгоритм (Рассоривать множество из n чисел(сложность 0(n2)), нахождение вершин, связанных цепочкой дуг(0(n+m)) и т.п.)
Класс Е:
Задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы полного графа.
Ни Р ни Е:
В условиях не содержится экспоненциальных вычислений, но для которых до сих пор не разработан точный и эффективный алгоритм, имеющий полиноминальную оценку (Решение систем уравнений с целочисленными переменными, оптимальный раскрой и т.п.)
