愚かな質問で申し訳ありません。記憶をたどることができず、グーグルはこの質問に答えるのに役立ちませんでした.
したがって、基本的にグラフ G(V,E) が与えられた場合、O(|V|^2) または O(|E|^2 + |V|^2) は多項式の複雑さと見なされ、O(| E|*|V|) 多項式も？そうでない場合、それはどのような複雑さですか? 疑似多項式でもないと思います。
もう 1 つの質問は、O(m*n) も多項式と見なされますか? m と n が問題への 2 つの独立した入力のサイズであるとしますか? ここで多項式時間の概念を明確にしたいだけで、O(m*n) がそのタイプの複雑さに対して別の名前を持っているかどうかを知りたいだけです。