求证：Θ符号的对称性及f(n)/g(n)=Θ(1)是否成立

让咱们逐个拆解这两个渐近复杂度的问题，用Θ符号的严格定义来分析，会清晰很多：

答案是肯定成立。

咱们先明确Θ符号的定义：如果$f(n) = \Theta(h(n))$，意味着存在两个正常数$c_1, c_2$和一个正整数$n_0$，使得对于所有$n \geq n_0$，都满足：
$$c_1 \cdot h(n) \leq f(n) \leq c_2 \cdot h(n)$$

因为$f(n)$和$h(n)$都是正函数（渐近复杂度讨论的都是正函数），我们可以把不等式两边同时除以$c_1$和$c_2$，得到：
$$\frac{1}{c_2} \cdot f(n) \leq h(n) \leq \frac{1}{c_1} \cdot f(n)$$

这里$\frac{1}{c_1}$和$\frac{1}{c_2}$显然也是正常数，而且当$n \geq n_0$时这个不等式同样成立。这完全符合$h(n) = \Theta(f(n))$的定义——所以这个结论是对的，Θ符号是对称的。

原命题：若$f(n) = \Theta(h(n))$且$g(n) = \Theta(h(n))$，则$\frac{f(n)}{g(n)} = \Theta(1)$ #

这个命题成立，咱们来严谨证明：

根据Θ的定义：

• 对于$f(n) = \Theta(h(n))$，存在正常数$c_1, c_2$和$n_1$，当$n \geq n_1$时，$c_1 h(n) \leq f(n) \leq c_2 h(n)$
• 对于$g(n) = \Theta(h(n))$，存在正常数$d_1, d_2$和$n_2$，当$n \geq n_2$时，$d_1 h(n) \leq g(n) \leq d_2 h(n)$

因为所有函数都是正的，我们可以做除法运算。取$n_3 = \max(n_1, n_2)$，当$n \geq n_3$时，两个不等式同时成立：
$$\frac{c_1 h(n)}{d_2 h(n)} \leq \frac{f(n)}{g(n)} \leq \frac{c_2 h(n)}{d_1 h(n)}$$

$h(n)$是正的，所以可以约掉，得到：
$$\frac{c_1}{d_2} \leq \frac{f(n)}{g(n)} \leq \frac{c_2}{d_1}$$

这里$\frac{c_1}{d_2}$和$\frac{c_2}{d_1}$都是正常数，完全符合$\frac{f(n)}{g(n)} = \Theta(1)$的定义——即这个比值被两个正的常数上下界限制，不会趋向无穷或0。

逆命题分析：若$\frac{f(n)}{g(n)} = \Theta(1)$，是否能推出$f(n) = \Theta(g(n))$（反之亦然）？ #

这个逆命题同样成立，而且这其实是$\Theta$符号的一个等价性质：

如果$\frac{f(n)}{g(n)} = \Theta(1)$，根据定义，存在正常数$A, B$和$n_0$，当$n \geq n_0$时：
$$A \leq \frac{f(n)}{g(n)} \leq B$$

因为$g(n)$是正函数，两边同时乘以$g(n)$，不等号方向不变：
$$A \cdot g(n) \leq f(n) \leq B \cdot g(n)$$

这直接满足$f(n) = \Theta(g(n))$的定义。反过来，如果$f(n) = \Theta(g(n))$，按照问题1的结论，$g(n) = \Theta(f(n))$，同样可以推出$\frac{g(n)}{f(n)} = \Theta(1)$，也就是$\frac{f(n)}{g(n)} = \Theta(1)$。

你提到的“二者相除结果为1”其实是一种简化说法，严格来说是相除的结果被两个正常数夹着，渐近趋向于一个非零常数，不一定恰好是1，但增长速度是相同的——这就是$\Theta$符号要表达的“渐近等价”的核心含义。

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