7

对不起愚蠢的问题。我无法记忆，谷歌搜索并没有帮助我回答这个问题。

所以基本上给定一个图 G(V,E)，我知道 O(|V|^2) 或 O(|E|^2 + |V|^2) 被认为是多项式复杂度，所以 O(| E|*|V|) 也是多项式吗？如果不是，它的复杂性是什么？我相信它也不是伪多项式。

另一个问题是：O(m*n) 是否也被视为多项式，给定 m 和 n 是问题的两个独立输入的大小？我只想在这里澄清多项式时间的概念，并想知道 O(m*n) 是否因其复杂性类型而有不同的名称。

4

1 回答 1

8

它是多项式 O(|V|^3)，因为边的数量是有界的 O(|V|^2)

于 2013-10-31T19:25:07.650 回答