大 O 表示法

1. 简介

在本文中，我们将介绍大 O 表示法的数学，并展示一个大 O 证明的示例。

2. 正式定义

定义： $$f(x) = O(g(x))$$表示存在两个正常数$$x_1$$和$$c$$，对于所有$$x \geq x_1$$使得$$0 \leq f(x) \leq cg(x)$$。

3. 第一个正常数：$$x_1$$

当说 $$f(x) = O(g(x))$$时，我们说**“ x的f是x的大 O g ”。**

不要让等号欺骗你：$$f(x)$$是一个函数，$$O(g(x))$$是一个集合。你不能有一个等于一个集合的函数。这就像说地球等于太阳系。更像是，地球属于（组成行星的一组）太阳系。类似地，$$f(x)$$属于称为$$O(g(x))$$的一组函数（x的big-O g）。

我们现在有两个函数—— $$f(x)$$和$$g(x)$$。函数以不同的速度增长 。例如，二次函数将比线性函数增长得更快。但有时，二次方需要一些时间才能赶上！

例如，如果我们有$$a(x) = 2x^2 + 2x + 1$$和$$b(x) = 10x$$，我们将有$$a(1) = 5$$和$$b(1) = 10$$。但是现在说我们选择$$x = 15$$。现在我们有$$a(15) = 450 + 30 + 1 = 481$$和$$b(x) = 150$$。更重要的是，对于任何大于$$x = 15$$的值，例如$$x = 20$$，$$a(x)$$将大于$$b(x)$$。 （现在是回顾正式定义的好时机；这是$$x \geq x_1$$部分）。

重要的是，对于正式理解 big-O 的情况，**我们并不特别关心$$a(x)$$在什么时候开始超过$$b(x)$$。**只是它确实如此，并且从那时起，它继续大于$$b(x)$$。

4. 第二个正常数：$$c$$

我们在上面看到了$$a(x)$$是如何赶上$$b(x)$$ 的。最终，它做到了，但需要一段时间。

它最终增长得更快的原因是因为$$2x^2$$项。或者，更准确地说，它的$$x^2$$部分。**这告诉我们$$a(x) = O(x^2)$$。**使用原始定义的符号：$$f(x) = a(x)$$和$$g(x) = x^2$$。

对于 big-O，我们不关心 $$a(x)$$中的其他项，或者2x 2项中的常数2。

再次查看我们在第 2 节中的定义，这就是常数$$c$$的用武之地。我们可以通过任何正常数缩放$$g(x)$$ ——只要$$f(x)$$保持小于缩放版本（超过某个点，$$x \geq x_1$$ )。

如果我们取 $$d(x) = 3x^3 + 2x + 10$$，我们需要找到$$c$$和 $$x_1$$的值，这样对于所有大于 $$x_1$$ 的值， $$ d(x) \leq cx^3 $$。这正是我们在第 4 节中执行。

5. 把碎片放在一起

为了证明 $$f(x) = O(g(x))$$，我们需要找到两个正常数$$c$$和$$x_1$$，对于所有 $$x \geq x_1$$ 使得 $$0 \leq f(x) \leq cg(x)$$。我们需要找到$$c$$和$$x_1$$的值，使得不等式成立。

这意味着，在某个点之后，$$g(x)$$的缩放版本将始终大于$$f(x)$$。

6. 例子

令 $$d(x) = 3x^3 + 2x + 10$$ 。

假设我们希望证明 $$d(x) = O(x^3)$$。这意味着我们需要找到两个正整数 $$c$$和 $$x_1$$,对于所有$$x \geq x_1$$使得$$0 \leq d(x) \leq cx^3$$。

好吧，我们知道 $$d(x) = 3x^3 + 2x + 10 \leq 3x^3 + 2x^3 + 10x^3 = 15x^3$$

所以，$$d(x) \leq 15x^3$$。

因此，如果我们设置$$x_1 = 1$$和$$c = 15$$，那么对于任何 $$x \geq x_1$$，我们都会得到这样的结果$$0 \leq d(x) \leq cx^3$$。所以$$d(x) = O(x^3)$$。

我们可以找到 满足上述条件的$$x_1$$和$$c$$的其他值。重要的是 存在满足条件的$$x_1$$和$$c$$的值。