最近一次让人们感到困惑的考试的复杂性
Complexity from a recent exam that confused people
您认为以下信息是否属实？
If Θ(f(n)) = Θ(g(n)) AND g(n) > 0 everywhere THEN f(n)/g(n) ∈ Θ(1)
我们和我们的教授有点争论
划分函数 f(n),g(n) 与划分他们的 Big-O 不同。例如让：
f(n) = n^3 + n^2 + n
g(n) = n^3
所以：
O(f(n)) = n^3
O(g(n)) = n^3
但是：
f(n)/g(n) = 1 + 1/n + 1/n^2 != constant !!!
[编辑 1]
但正如 kfx 指出的那样，您正在比较复杂性，因此您需要：
O(f(n)/g(n)) = O(1 + 1/n + 1/n^2) = O(1)
所以答案是肯定的
但要注意复杂性理论并不是我的菜，而且我对你的问题没有任何背景。
使用Landau记法的定义https://en.wikipedia.org/wiki/Big_O_notation，很容易得出结论，这是真的，除法的极限必须小于无穷大但大于0。
它不必完全是 1 但它必须是一个有限常数，即 Θ(1)。
一个反例会很好，如果陈述不正确，应该很容易给出。一个积极的严格证明可能需要从酸橙相对于系列的定义出发，以证明形式定义和极限定义的等价性。
我使用这个定义并且没有看到它被证明是错误的。我想分歧可能在于 Θ 的确切定义，众所周知，人们口语化地使用它们时差异很小，尤其是 Big O。或者可能是一些棘手的案例。对于正向定义的函数和系列，我认为它不会失败。
f(n) = Θ(g(n)) 表示有 c, d, n0 使得 cg(n) <= f(n) <= dg(n) for n > n0.
然后，因为 g(n) > 0，c <= f(n)/g(n) <= d for n > n0.
所以 f(n)/g(n) = Θ(1).
基本上任何一对函数都有三个选项f, g：要么第一个渐进变慢，然后我们写f=o(g)（注意我是使用小 o)，第一个 渐近 增长得更快：f=ω(g)（同样是小 omega）或者它们渐近紧束缚：f=Θ(g).
f=o(g) 的意思比大 O 更严格，因为它不允许 f=Θ(g) 为真； f=Θ(g) 意味着 f=O(g) 和 f=Ω(g)，但 o, Θ 和 ω 是互斥的。
要确定 f=o(g) 是否足以评估 n 趋于无穷大的极限 f(n)/g(n) 如果它为零，则 f=o(g) 为真，如果它为无穷大 f=ω(g) 是真的，如果它是任何有限实数，f=Θ(g) 就是你的答案。 这不是定义，而只是一种评估语句的方法。 （我在这里做的一个假设是 f 和 g 都是正数。）
特殊情况是如果 n goint 的极限 f(n)/1 = f(n) 是有限数，则表示 f(n)=Θ(1)（基本上我们为 g 选择常数函数）。
现在我们开始解决您的问题：由于 f=g(Θ) 蕴含 f=O(g)，我们知道存在 c>0 和 n0 使得 f(n) <= c*g(n)对于所有 n>n0。因此我们知道 f(n)/g(n) <= (c*g(n))/g(n) = c 对于所有 n>n0。 Ω 也可以用相反的不等号来做同样的事情。因此，我们从某些 n0 中得到 f(n)/g(n) 介于 c1 和 c2 之间，由于 Θ 的定义方式，这些 n0 被认为是有限数。因为我们知道我们的新函数在那里的某个地方，我们也知道它的极限是有限的，从而证明它确实是常数。
结论，我相信你是对的，我希望你的教授提供反例来反驳这个说法。如果有什么不明白的地方，请随时在评论中提出更多问题，我会尽力澄清。
您认为以下信息是否属实？
If Θ(f(n)) = Θ(g(n)) AND g(n) > 0 everywhere THEN f(n)/g(n) ∈ Θ(1)
我们和我们的教授有点争论
划分函数 f(n),g(n) 与划分他们的 Big-O 不同。例如让：
f(n) = n^3 + n^2 + n
g(n) = n^3
所以：
O(f(n)) = n^3
O(g(n)) = n^3
但是：
f(n)/g(n) = 1 + 1/n + 1/n^2 != constant !!!
[编辑 1]
但正如 kfx 指出的那样，您正在比较复杂性，因此您需要：
O(f(n)/g(n)) = O(1 + 1/n + 1/n^2) = O(1)
所以答案是肯定的
但要注意复杂性理论并不是我的菜，而且我对你的问题没有任何背景。
使用Landau记法的定义https://en.wikipedia.org/wiki/Big_O_notation，很容易得出结论，这是真的，除法的极限必须小于无穷大但大于0。
它不必完全是 1 但它必须是一个有限常数，即 Θ(1)。
一个反例会很好，如果陈述不正确，应该很容易给出。一个积极的严格证明可能需要从酸橙相对于系列的定义出发，以证明形式定义和极限定义的等价性。
我使用这个定义并且没有看到它被证明是错误的。我想分歧可能在于 Θ 的确切定义，众所周知，人们口语化地使用它们时差异很小，尤其是 Big O。或者可能是一些棘手的案例。对于正向定义的函数和系列，我认为它不会失败。
f(n) = Θ(g(n)) 表示有 c, d, n0 使得 cg(n) <= f(n) <= dg(n) for n > n0.
然后，因为 g(n) > 0，c <= f(n)/g(n) <= d for n > n0.
所以 f(n)/g(n) = Θ(1).
基本上任何一对函数都有三个选项f, g：要么第一个渐进变慢，然后我们写f=o(g)（注意我是使用小 o)，第一个 渐近 增长得更快：f=ω(g)（同样是小 omega）或者它们渐近紧束缚：f=Θ(g).
f=o(g) 的意思比大 O 更严格，因为它不允许 f=Θ(g) 为真； f=Θ(g) 意味着 f=O(g) 和 f=Ω(g)，但 o, Θ 和 ω 是互斥的。
要确定 f=o(g) 是否足以评估 n 趋于无穷大的极限 f(n)/g(n) 如果它为零，则 f=o(g) 为真，如果它为无穷大 f=ω(g) 是真的，如果它是任何有限实数，f=Θ(g) 就是你的答案。 这不是定义，而只是一种评估语句的方法。 （我在这里做的一个假设是 f 和 g 都是正数。）
特殊情况是如果 n goint 的极限 f(n)/1 = f(n) 是有限数，则表示 f(n)=Θ(1)（基本上我们为 g 选择常数函数）。
现在我们开始解决您的问题：由于 f=g(Θ) 蕴含 f=O(g)，我们知道存在 c>0 和 n0 使得 f(n) <= c*g(n)对于所有 n>n0。因此我们知道 f(n)/g(n) <= (c*g(n))/g(n) = c 对于所有 n>n0。 Ω 也可以用相反的不等号来做同样的事情。因此，我们从某些 n0 中得到 f(n)/g(n) 介于 c1 和 c2 之间，由于 Θ 的定义方式，这些 n0 被认为是有限数。因为我们知道我们的新函数在那里的某个地方，我们也知道它的极限是有限的，从而证明它确实是常数。
结论，我相信你是对的，我希望你的教授提供反例来反驳这个说法。如果有什么不明白的地方，请随时在评论中提出更多问题，我会尽力澄清。