假设我们有两个单调递增的函数f和g,使得f(n)=Ω(n)且f(g(n))=O(n),那么我想得出结论g(n)=O(n)。这种说法正确吗?
我认为这是一个错误的说法,我一直试图提供反例来证明这是错误的说法,但尝试了很多次后,我开始持不同看法。
请问,如果这是一个错误的说法,你能否提供一些解释或示例,或者如果这是一个正确的说法,是否有一种证明方法。
假设我们有两个单调递增的函数f和g,使得f(n)=Ω(n)且f(g(n))=O(n),那么我想得出结论g(n)=O(n)。这种说法正确吗?
我认为这是一个错误的说法,我一直试图提供反例来证明这是错误的说法,但尝试了很多次后,我开始持不同看法。
请问,如果这是一个错误的说法,你能否提供一些解释或示例,或者如果这是一个正确的说法,是否有一种证明方法。