提问人：Alexander Cabrera 提问时间：7/27/2023 最后编辑：trincotAlexander Cabrera 更新时间：7/27/2023 访问量：107
Big O（渐近运行时间），是 3^n = O（2^n）？
Big O (Asymptotic run time), is 3^n = O(2^n)?
问：
我正在学习一门课程，该课程给出了 （100033）3n 的示例函数。除了以下内容外，它没有给出任何解释：
对于指数函数，指数的系数与评估函数的增长无关，因此渐近运行函数通常表示为 2n。因此，f（n）=（100033）3n 的渐近运行时间函数为 2n。
然后它给出了另一个例子 f（n）=3n+2n。对于这个例子，它说：
我们可以忽略 2N，因为 3 N 更大，渐近运行时间为 3N。
然而，在忽略 2 n 之后，我们只剩下 3 n，它是指数的，如果我遵循第一个示例的逻辑，因为 3 n 是指数的，这不意味着它的渐近运行时间是 2 n 吗？
我是一个初学者，这本书没有解释为什么这些工作背后的任何数学原理。所以我只是在应用这本书给我的逻辑。
答：
2赞
trincot
7/27/2023
#1
您引用的文本提出了错误的主张：
因此，f（n）=（100033）^3n 的渐近运行时函数为 2^n
这是错误的。的确，在查看渐近运行时间时，可以去除乘以 n 的正系数，因此
f（n） = 1000333n 是 O（100033n)
但是不能减少幂的基数：
f（n） 不是 O（2n)
证明 3 n 不是 O（2n)
我们可以用大O的定义来证明这一点。
假设 f（n） = 3 n，我们想看看 f（n） 是否为 O（2n）。然后，我们应该能够找到常数 M 和 N，这样：
3 n ≤ M（2 n） 用于所有n > N
让我们来玩一下这个约束：
(3/2)n ≤ M 用于所有 n > N
艺术
n ≤ 对数3/2M 对于所有 n > N
...这是一个矛盾。“all n > N”意味着我们可以选择 n 作为大于log 3/2M 的某个值。这违反了约束。
结论是 f（n） = 1000333n 不是 O（2n），而您引用的文本在该声明中是错误的。
书中的第二句话是正确的：
当我们有 f（n） = 3 n + 2 n 时，我们可以去掉第二项，因为第一项比第二项渐近大，所以我们可以说 f（n） 是 O（3n）。
渐近复杂度规则
总之，如果 a 和 b 是正常数，则：
abn 是 O（an)
但是，如果 b > 1：
（ab） n 不是 O（an)
对于 a 和 b（2 和 1.5）的具体值：
21.5n 是 O（2n)
但：
3 n 不是 O（2n)
上一个：有没有对“补丁”进行建模的类？
下一个：二进制数据的测序概率
评论