如果一个函数 A 调用 n^c 个函数 B 并且在 O(n^2) 时间内运行，那么函数 A 的时间复杂度是多少？它只是多项式 (n^c) 以及 c 刚刚变大吗？
问问题
404 次
1 回答
5
如果一个函数A调用另一个函数B，则总复杂度是A和B的复杂度的乘积。所以在这种情况下，总复杂度为 O( n c · n 2 ) = O( n c + 2 )。
产品的一般规则：
ƒ 1 ∈ O( g 1 ) 和 ƒ 2 ∈ O( g 2 ) ⟹ ƒ 1 ·ƒ 2 ∈ O( g 1 · g 1 )
ƒ·O( g ) ∈ O(ƒ· g )
于 2010-10-13T06:32:14.817 回答