algorithm - 是 ϴ(n)/n = ϴ(1) 吗？

Question

我遇到了以下等式:

那么 ϴ(n)/n(或 ϴ(n)/(n+1))= ϴ(1)？如果是，请通过示例帮助我理解其原因。

Answer 1

ϴ(n) 表示复杂度的算法，例如 n、2n、3n、4n 等 您可以将 ϴ(n) 视为代表类似 kn 的东西，其中 k 为正实数。

kn/n 当然是 k，您同样可以将其视为 strong>ϴ(1)代表。

kn/(n+1) 在 k 上收敛为 n->∞。您可以使用 L'Hopital's 来确认这一点。

如果您是 Big-Theta 和 Big-O 的新手，将 ϴ(n) 理解为“n 的顺序”会有所帮助；同样，ϴ(n²)，“在 n 平方的数量级上”；等等。

编辑: 请注意，我的回答语气是故意不正式的。准确的概念化是从边界函数的角度来思考 ϴ(n)。请参阅下面的 Paul Hankins 评论。虽然在日常使用中我认为上述理解是有帮助的，但我建议您听取他的建议和关注。

为了确保至少他的一些笔记也在这里出现，我补充说 O 复杂度的正式定义如下:

A function f(x) can be said to be O(g(x)) if there exists |f(x)| <= Mg(x) ∀ x >= x₀ where M is a positive real number.

ϴ(g(x)) also satisfies |f(x)| >= Mg(x) ∀ x >= x₀ where M is a positive real number.

希望这与上面的示例相比没有太大的飞跃。你现在可以提出这个问题:一个函数的边界是 M_ax 除以 x 以 M_b(1) 为界？