Big-Theta符号分析：求解第二个问题的合适反例

首先明确第二个命题的内容：

If ( f(n) = \Theta(h(n)) ) and ( g(n) = \Theta(h(n)) ), then ( f(n)^{g(n)} = \Theta(h(n)^{g(n)}) )

我们可以通过构造具体函数来推翻这个命题，步骤如下：

• 定义基础函数：( h(n) = n )
• 构造 ( f(n) = 2n )：显然 ( f(n) = \Theta(h(n)) )，因为存在正常数 ( c_1=1 )、( c_2=2 )，当 ( n \geq 1 ) 时，( 1 \cdot n \leq 2n \leq 2 \cdot n )，完全符合大Θ的定义。
• 构造 ( g(n) = n )：同样 ( g(n) = \Theta(h(n)) )，使用和上面相同的常数即可验证。

接下来分析函数的幂次形式：

• ( f(n)^{g(n)} = (2n)^n = 2^n \cdot n^n )
• ( h(n)^{g(n)} = n^n )

现在验证是否满足 ( f(n)^{g(n)} = \Theta(h(n)^{g(n)}) )：
根据大Θ的定义，需要存在正常数 ( c_1' )、( c_2' ) 和 ( n_0 )，使得当 ( n \geq n_0 ) 时：
( c_1' \cdot n^n \leq 2^n \cdot n^n \leq c_2' \cdot n^n )

我们看右边的不等式：两边同时除以 ( n^n )（正数，不等号方向不变），得到 ( 2^n \leq c_2' )。但 ( 2^n ) 是指数增长函数，随着n增大会趋向无穷大，不可能被一个固定的常数 ( c_2' ) 限制住。因此不存在这样的 ( c_2' )，说明 ( (2n)^n ) 不属于 ( \Theta(n^n) )。

这就完美构成了第二个命题的反例——满足前提条件，但结论不成立。

内容的提问来源于stack exchange，提问作者user6797155