我有这个功能:
f(n) = g(n) + h(n)
g(n) > h(n)
对于大 O 表示法，这个结果总是正确的吗？ O(g(n))
谢谢。
最佳答案
是的，这是正确的，因为g(n) + h(n) < g(n) + g(n) <= 2*g(n) , 所以你找到了一个常量 C=2这样 f(n) <= C*g(n) (对于足够大的值 n )，并通过 definition of big O , 表示 f(n)在O(g(n))
关于algorithm - g(n) > h(n) 的大 O 表示法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28739817/