Существует несколько классов задач, для которых легко просчитывается необходимая вычислительная мощность и зависимость между размерностью задачи и количеством вычислений. 1) Линейная зависимость: N ~ n
N – количество вычислений;
n – размерность. 2) Показательная зависимость (полиномиальная): N ~ n^x
X = 1,2,3,… 3) Экспоненциальная: N ~ A^n
Это касается в значительной степени задач с известным и строгим алгебраическим расчетом. Существуют задачи, которые с трудом (или условно) могут быть отнесены к какому-либо классу, задачи, у которых отсутствует четкий алгоритм решения, а иногда и вообще не имеющих алгоритма решения, такие задачи принято называть интеллектуальными. Например, поиски путей на графах, составление расписания, диагностика, принятие решений в условиях неопределенностей.
где ^ - здесь и далее - степень