algorithm - 数量级的链式法则

Question

我正在寻找类似数量级的链式规则。认为：

y = O(x)
z = O(y)

然后：

z = O(x)

但我们可以比这更通用。如果 p 是多项式：

y = O(x)
z = O(p(y))

然后：

z = O(p(x))

这些似乎都不难证明。但是我们可以进一步概括这一点吗？

标签： algorithmbig-o

Answer 1

证明很简单。假设p(y) = an y^k + ... + a1 y + a0。因为，y = O(x)有一个常数c。y < c*x因此，p(y) < an*c^k x^k + + ... + a1*c x + a0 = f(x)。如果c <= 1，p(y) < p(x)如f(x) <= p(x)。如果c > 1，我们可以说p(y) < c^k p(x)。因此，有一个常数c' = c^k使得p(y) < c' p(x)。因此，p(y) = O(p(x))。

最终，z = O(p(y))我们证明了z = O(p(x))。

要获得更精确的证明，您可以对多项式的次数使用数学归纳法p(x)。

为了概括这种情况，我们应该尝试找到具有特定属性的函数，即f(y) < c' f(x)if y < c x。功能的一大类f(x)是增加，和f(cx) = \Theta(f(x))。因此，所有这些函数都满足传递性。例如，f(x) = sqrt(x)满足约束，但f(x) = 2^x不满足。