如何证明|sin(n!)|=Θ(1)？算法与数据结构课程问题求证

先明确算法分析中大Θ符号的严格定义：
存在正的常数c₁、c₂和整数n₀，使得对所有n ≥ n₀，都有：
c₁ ≤ |f(n)| ≤ c₂
此时称f(n) = Θ(1)。

1. 上界的证明（|sin(n!)|=O(1)） #

这部分很直接：正弦函数的基本性质决定了对任意实数x，|sin(x)| ≤ 1。对于x = n!，显然|sin(n!)| ≤ 1恒成立。取c₂=1、n₀=1，所有n≥1都满足这个不等式，所以|sin(n!)|属于O(1)。

2. 下界的矛盾（无法证明|sin(n!)|=Ω(1)） #

要满足Θ(1)，还需要找到正的常数c₁，让所有足够大的n都有|sin(n!)| ≥ c₁，但这做不到：
π是无理数，根据Dirichlet逼近定理，存在无限多组整数k和n，使得|n! - kπ|可以任意小。此时：
sin(n!) = sin(kπ + (n! - kπ)) = (-1)^k · sin(n! - kπ)
当|n! - kπ|趋近于0时，sin(n! - kπ) ≈ n! - kπ，所以|sin(n!)|会无限趋近于0。这意味着不存在固定的c₁>0，能覆盖所有足够大的n。

结论 #

严格来说，|sin(n!)|只能被证明为O(1)，但不满足Ω(1)的要求，因此**|sin(n!)| ≠ Θ(1)**。如果题目认为该结论成立，大概率是混淆了“有界函数”和大Θ符号的严格定义——部分非严谨语境中会把有界函数笼统称为Θ(1)，但这不符合算法分析的标准定义。

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