ϴ(n)/n = ϴ(1)吗？

Question

我遇到了以下方程：

那么 ϴ(n)/n（或 ϴ(n)/(n+1)）= ϴ(1) 吗？如果是，请给我举一个例子来帮助我理解原因。

- Bhavesh

---

这是给数学网站的吗？ - Fattie

你好！数学问题不属于StackOverflow的讨论范围。请查看[帮助/主题]以了解可以在此处提出哪些问题。你可能可以在[Math.SE] StackExchange上提问，但在提问之前请务必仔细阅读他们的发布指南。 - Brian61354270

我建议关闭这个问题，因为它不是符合[帮助/主题范围]中定义的编程问题。 - Brian61354270

这更多是关于计算机科学/算法理论的问题，而非数学问题。 - jxh

@jxh 我同意。我认为数学Stack Exchange可能会对这个问题不屑一顾。此外，我认为Bhavesh想要一些代码示例。 - lmonninger

Answer 1

ϴ(n) 表示算法的复杂度，例如 n, 2n, 3n, 4n 等。你可以把 ϴ(n) 看作类似于 kn 的表示方法，其中 k 是正实数。

kn/n 当然是 k，你也可以把它看作是 ϴ(1) 的表示。

kn/(n+1) 随着 n->∞ 收敛于 k。你可以使用 L'Hopital 定理来确认这个结果。

如果你对大O和大θ还不太了解，那么可以把 ϴ(n) 理解为“n的数量级”，同样的，ϴ(n²) 就是“n平方的数量级”，以此类推。

编辑： 请注意，我的回答意图是非正式的。正确的概念化方式是将 ϴ(n) 视为边界函数。请参考下面Paul Hankins的评论。虽然在日常使用中，我认为以上理解很有帮助，但是建议你遵从他的建议和担忧。

为了确保这里至少包含他的一些笔记，我补充说大O复杂度的正式定义如下：

如果存在一个正实数 M，使得对于所有的 x >= x₀，都满足 |f(x)| <= Mg(x)，则函数 f(x) 可以称为 O(g(x))。

同时，如果存在一个正实数 M，使得对于所有的 x >= x₀，都满足 |f(x)| >= Mg(x)，则函数 f(x) 可以称为 ϴ(g(x))。

希望以上内容不会给你造成太大困扰。现在你可以提出这样一个问题：一个被 M_ax 限制并且除以 x 后被 M_b(1) 限制的函数是否有界？

- lmonninger

---

这个答案已经有赞成票并被接受，但其中有些东西我认为仍然令人困惑，即使答案的意图是有帮助的。Theta(n)不像kn那样，它是一组函数，其数量级（最终）在线性函数之上和之下被限制。Theta(1)不是“基本上”一个常数——它是一组函数，它们的数量级最终被上下常数所限制。例如，|cos(n)|n + 5n|sin(n)|是Theta(n)，但不像任何k的kn。 - Paul Hankin

我理解像这样的答案的意图 - 实际定义需要一些理解工作，通过简化概念直到它们易于理解而不需要太多工作，可以对复杂性有所感觉。但是，从事实上偏离实际定义的简化解释最多只是实际理解的一个踏板，在实践中，人们对复杂性到底是什么存在如此多的混淆，以至于我认为它们没有帮助。 - Paul Hankin

我同意你的观点。为了更精确地理解，最好考虑有界函数的概念。也许最好写出这样的答案，那么我的回答可以成为你的一个跳板。 - lmonninger

如果这更接近您认为的适当，请告诉我。 - lmonninger

我不会在这个问题上进一步参与，因为我已经说了我认为重要的事情。然而，我会说你对大Theta的定义实际上是大O的定义。 - Paul Hankin