algorithm - 算法分析中如何判断一个函数是否属于特定的渐近类型？

Question

我想更好地理解渐近符号以及如何分类一个函数是否是另一个函数的 O 符号，以及我们如何判断 f = o(g) || f != o(g)

例如:

---

---

例如，我们如何知道 f = O(g)？

我见过的主要是这种方法(下面的解决方案与上面的问题无关):

但这很令人困惑，因为我不明白证明这一点的方式。

请帮助我理解这里应用的核心概念。

谢谢

Answer 1

如果我们能找到这两个东西，我们就说 f 是 O(g):

(1) 我们可以找到一个常量“C”(你只选择一个 constnat ，这里我的意思是你以后不能改变它，这是初学者最困惑的部分)。

(2) 和一个“N”(这是一些下限，意味着对于大于此 N 的值，我们的公式将有效，一旦你到达终点然后回来并尝试理解我的意思是下限)。

这样每当我们插入 n>= N 的值时，f(n) 应该小于或等于 C.g(n)

或者公式形式:

示例:

假设我有一个函数 f = 3n^2 + 4n + 3

还有一个功能g = n^2

是f = O(g)吗？

f 的首项是3n^2 ，这意味着如果我有一个高于 3 的常数我将它乘以 g然后 f将小于 g .

我们以n = 4 > 3为例然后我得到g = 4n^2和我的常数c然后是4 .

现在的问题是如果我增加 n 的值会发生什么？例如，如果我插入 n = 4然后 f(n)不会小于g(n)但是当我插入 n = 5那么它是有效的。所以在这个例子中 c = 4 and N = 5 .

现在您的问题中有两个不同的内容。下面这个问题与Big-O notation无关，它被称为tilde notation .

Big-O 抛弃了常数项，但代字号没有。它是算法比较的更严格的形式。这里22意味着每当 n 接近无穷大时，f 和 g 之间的差异约为 22。但是我更喜欢 tilde表示法，但首先您需要了解 Big-O，然后才能更进一步。

对于你的这个问题:

可以看到:两个函数都有高项n即f = 7n + ...和 g = n .如果我想证明是f is o(g)

现在如果我要求什么值c c.g(n)大于 f(n) .是否存在常量 c这样公式对所有 n >= some N 都有效.

如果我乘以 g现在 7 (因为 f 的前导常数为 7)这有效吗？不，因为 f 也有 8 个因子，这意味着我需要增加常量 c .让我们把它当作8然后还是7n + 8 > 8n如果n = 1但是当 n >= 2 时会发生什么？然后 g总是大于 f .所以对于常量 c = 8 and n >= 2 f is o(g) .你也可以证明 g is O(f) .这不难，你应该得到常数c = 1 and for n belonging to natural number