В графе сложность O (n * m) считается полиномиальной или как?

Question

Я пытаюсь понять, считается ли O (n * m) полиномиальным, учитывая, что m и n имеют размеры двух независимые входы?

Я просто хочу уточнить здесь понятие полиномиального времени и хочу знать, имеет ли O (n * m) другое название для своего типа сложности.Как мы представим это на графике?

Answer 1

Допустим, что m> n.Тогда O(n*m) < O(m^2), причем последний явно полиномиален.Таким образом, O (n * m) также является полиномом.

Answer 2

Да, это полином.В основном, пока вы не видите n и m как показатели в Big O, это полином.

Вы можете видеть это так:

• полиномиальный .При сложности алгоритм описывается некоторой полиномиальной функцией.(например, O(n*m), O(n^3 * log m) и т. д.)

• Экспоненциальная .При сложности алгоритма описывается некоторая экспоненциальная функция.(например, O(m * 2^(n)), O(3^n * log m) и т. д.)