大 O 符号的 2^n 或 n^2 中的主导项是什么
Whats the dominant term in 2^n or n^2 for big O notation
我一直在研究 Big O 表示法并遇到了一个操作计数 2^n+n^2。我知道大 O 表示法的做法是删除常量和低阶项，但是我无法弄清楚要制作哪一个 O(n)。我认为可能是 2^n，但没有找到任何建议。
2^n 占优势，因为 n 越大它增长得越快。
查看随时间变化的增长因子。对于 n 的前八个值，O(n^2) 计算为：
0、1、4、9、16、25、36、49...
O(2^n) 产生二的幂：
1、2、4、8、16、32、64、128...
哪个增长更快应该是相当明显的。
请注意，即使底数和指数不同，一般规则也适用。对于较小的 n，O(1.1^n) 最初的工作量可能低于 O(n^10)，但随着 n 接近无穷大，所有指数大于 1 的指数增长最终将超过固定指数多项式增长。
TIL：用 SO 写数学真是痛彻心扉！
我非常喜欢@ShadowRanger对你问题的回答。但是，我想再展示一个问题的观点。
如果您看一下这张图，绿色部分是 2^n，红色部分是 n^2。如果你能看到，一开始，线 n^2 比 2^n 增长得更快，但随着你变大，线交叉并且 2^n 开始变得更大，更快。
因此，n-->∞（当 n 变得非常大）时，2^n 大于 n^2。
根据 L'Hopital 的规则：
lim_{n -> infinity} (n^2 / 2^n )
= 1/log(2) lim_{n -> infinity} (2n / 2^n)
= 1/log(2)^2 lim_{n -> infinity} (2 / 2^n)
= 0
我们有 n^2 = o(2^n)，这意味着 n^2 = O(2^n)。
如果这个证明没有意义：根据定义，f(n) = O(g(n) 当且仅当 f(n) 在 n 增长后限制在 g(n) 的某个常数倍内过去一些常数。考虑 f(n) = o(g(n)) 的一种方式是，随着 n 增长到无穷大，g(n) 将继续增长得更快，超过 f(n)。换句话说：
f(n) = o(g(n)) 当且仅当极限 f(n)/g(n) 在 n 趋于无穷大时变为零。
o(g(n) 是比 f(n) = O(g(n)) 严格更强的条件。
或者，您只需要直接使用定义：找到一些 a 和 b 使得 n^2 <= a | 2^n | 对所有 n >= b，这是简单的代数运算。
我一直在研究 Big O 表示法并遇到了一个操作计数 2^n+n^2。我知道大 O 表示法的做法是删除常量和低阶项，但是我无法弄清楚要制作哪一个 O(n)。我认为可能是 2^n，但没有找到任何建议。
2^n 占优势，因为 n 越大它增长得越快。
查看随时间变化的增长因子。对于 n 的前八个值，O(n^2) 计算为：
0、1、4、9、16、25、36、49...
O(2^n) 产生二的幂：
1、2、4、8、16、32、64、128...
哪个增长更快应该是相当明显的。
请注意，即使底数和指数不同，一般规则也适用。对于较小的 n，O(1.1^n) 最初的工作量可能低于 O(n^10)，但随着 n 接近无穷大，所有指数大于 1 的指数增长最终将超过固定指数多项式增长。
TIL：用 SO 写数学真是痛彻心扉！
我非常喜欢@ShadowRanger对你问题的回答。但是，我想再展示一个问题的观点。
如果您看一下这张图，绿色部分是 2^n，红色部分是 n^2。如果你能看到，一开始，线 n^2 比 2^n 增长得更快，但随着你变大，线交叉并且 2^n 开始变得更大，更快。
因此，n-->∞（当 n 变得非常大）时，2^n 大于 n^2。
根据 L'Hopital 的规则：
lim_{n -> infinity} (n^2 / 2^n )
= 1/log(2) lim_{n -> infinity} (2n / 2^n)
= 1/log(2)^2 lim_{n -> infinity} (2 / 2^n)
= 0
我们有 n^2 = o(2^n)，这意味着 n^2 = O(2^n)。
如果这个证明没有意义：根据定义，f(n) = O(g(n) 当且仅当 f(n) 在 n 增长后限制在 g(n) 的某个常数倍内过去一些常数。考虑 f(n) = o(g(n)) 的一种方式是，随着 n 增长到无穷大，g(n) 将继续增长得更快，超过 f(n)。换句话说：
f(n) = o(g(n))当且仅当极限f(n)/g(n)在n趋于无穷大时变为零。o(g(n)是比f(n) = O(g(n))严格更强的条件。
或者，您只需要直接使用定义：找到一些 a 和 b 使得 n^2 <= a | 2^n | 对所有 n >= b，这是简单的代数运算。