performance - 大 O 复杂度：T(n) = O(f(n))，G(n) = O(h(n))。T(G(n)) = O(h(f(n)))？

Question

T(n)= O(f(n)), G(n)= O(h(n))

我将如何证明或反驳：

  T(G(n))= O(h(f(n))

我认为这是错误的，因为它应该是 O(f(h(n))) 而不是 O(h(f(n)))，因为在应用 T 之前应用了 G，所以我尝试用多项式函数代替 T 和G，我认为顺序很重要，（n^2）！不等于 (n!)^2 ，但我不确定这个推理是否正确？

标签： performancetimebig-o

Answer 1

你是对的，这是错误的，但是我不太明白你的反例。
一个反例是取一个函数及其逆函数，同时保持 h 渐近非常小：

T(n) = 2^n , f(n) = 2^n这符合给定的事实2^n = O(2^n)
And
G(n) = lg(n!) , h(n) = n lg(n)This 也符合给定的事实lg(n!) < O(lg n^n) = O(n lg n)

但是，T(G(n)) = 2^(lg(n!)) = n!但是h(f(n)) = 2^n lg(2^n) = n*2^n，n! =/= O(n*2^n)因为我们有一个阶乘函数与一个指数函数（乘以一个线性函数），因此我们证明它是不正确的。

---

原因n! =/= O(n 2^n)是：n*2^n < 2^n * 2^n = 4^n而且我们知道阶乘函数“击败”指数。