NP или P означает, может ли оно быть решено за полиномиальное время в недетерминированной машине (NP) или в детерминированной машине (P).Это отражает сложность проблемы, но не сложность алгоритма, который решает проблему.
Хотя O (n ^ 2) означает, что анализируемый алгоритм для решения проблемы имеет верхнюю границу n ^ 2Сложность, когда n является входным.
Тета (n ^ 2) также является способом выражения сложности алгоритма, используемого для решения проблемы, но Тета (n ^ 2) в отличие от O (n ^ 2)) означает, что нижняя и верхняя границы сложности - это n ^ 2.
Существует также другая мера, которая o (little-oh), которая указывает на сложность нижней границы алгоритма.
Тета более точна, потому что, как O (n ^ 2) означает только верхнюю границу, алгоритм также O (n ^ 3) и O (n!).