找到尽可能紧的界限？
Find the bounds as tight as possible?
2^n −8 = O(2^n)
It says there are some positive constants c and n0 for which
0 <= f(n) <= cg(n) for all n >= n0
我将其解决为：
2^n −8 <= c2^n
If c = 1, and n0 = 1
1-8 <= 1*1
-7<= 1
then for all n >= n0 it remains true.
这是真的，但我不明白 Find the bounds as tight as possible 是什么意思？
谁能解释一下？
尽可能紧意味着找到一个函数g(n)具有最小增长阶数使得它仍然满足f(n) = O(g(n))。在您的示例中，它相对简单（因此我相信您会感到困惑）-只需删除增长最快的术语 (2^n) 以外的所有内容。
然而，让我们考虑一个示例，其中最紧的界限可能不是很明显 - 斐波那契数列生成器：f(n) = f(n - 1) + f(n - 2)。找到上限的一种简单方法是进行近似，将 n - 2 替换为 n - 1 得到 f(n) ≈ 2 * f(n - 1)，即 O(2^n)。这不是 最紧的 界限 - 通过求解二次方程，您会发现最紧的界限实际上是 Ө(1.61...^n) - 有关更多详细信息，请参阅 this page。
2^n −8 = O(2^n)
It says there are some positive constants c and n0 for which
0 <= f(n) <= cg(n) for all n >= n0
我将其解决为：
2^n −8 <= c2^n
If c = 1, and n0 = 1
1-8 <= 1*1
-7<= 1
then for all n >= n0 it remains true.
这是真的，但我不明白 Find the bounds as tight as possible 是什么意思？ 谁能解释一下？
尽可能紧意味着找到一个函数g(n)具有最小增长阶数使得它仍然满足f(n) = O(g(n))。在您的示例中，它相对简单（因此我相信您会感到困惑）-只需删除增长最快的术语 (2^n) 以外的所有内容。
然而，让我们考虑一个示例，其中最紧的界限可能不是很明显 - 斐波那契数列生成器：f(n) = f(n - 1) + f(n - 2)。找到上限的一种简单方法是进行近似，将 n - 2 替换为 n - 1 得到 f(n) ≈ 2 * f(n - 1)，即 O(2^n)。这不是 最紧的 界限 - 通过求解二次方程，您会发现最紧的界限实际上是 Ө(1.61...^n) - 有关更多详细信息，请参阅 this page。