为什么在定义 Θ 时 f(n) 和 g(n) 需要是非负函数

Question

在阅读 CLRS 中有关 Θ 的定义时。我发现

The definition of Θ(g(n)) requires that every member f(n) ∈ Θ(g(n))  be
asymptotically nonnegative, that is, that f(n) be nonnegative whenever n is 
sufficiently large. Consequently, the function g(n) itself must be 
asymptotically nonnegative, or else the set Θ(g(n))  **is empty.**

一正一负，不可能让我们做渐近分析。（这里Θ(g(n))可以是空集）。

但是

如果两个函数都为负，则应该不是问题，并将计入有效分析。为什么作者对 Θ 施加这样的限制。这没用吗？

Answer 1

允许负函数会使等价定义复杂化，实际上使它们不等价：

f(n) 在 O(g(n)) 中，如果有常量 N,C 这样对于所有 n > N: f(n) <= C*g(n)
f(n) 在O(g(n)) if limsup f(n)/g(n) < infinity when n->infinity

然后让我们看一下两个渐近负函数。

f(n) = -(n^2)
g(n) = -n

根据定义1：

for all n > 2, and with constant 1:
-(n^2) <= 1*-n 
And thus -(n^2) is in O(-n)

根据定义2：

limsup -(n^2) / -n = n = infinity    when  n -> infinity
So, -(n^2) is not in O(-n)

底线：这个定义消除了这种复杂性，同时又不失去大 O 表示法分析算法的任何用处，这是本书的主要重点。

（需要说明的是，这可能可以通过巧妙的定义解决方法来解决，但这只会使事情不必要地复杂化，而作者可能希望避免这种情况）。

为什么在定义 Θ 时 f(n) 和 g(n) 需要是非负函数

Why does f(n) and g(n) needs to be non-negative function while defining Θ

algorithm

big-o

analysis

asymptote