0

在阅读 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)) 在这里可以是一个空集）。

但

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

4

1 回答 1

1

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

  1. f(n)如果O(g(n))有常数N,C使得所有n > N:f(n) <= C*g(n)
  2. f(n)O(g(n))如果在limsup f(n)/g(n) < infinity 什么时候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 符号对分析算法的有用性，这是本书的主要重点。

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

于 2020-05-14T08:05:04.750 回答