大 O 符号：定义
Big O Notation: Definition
我一直在看麻省理工学院的算法课程讲座，大 O 符号的定义说
f(n) = O(g(n)) 这样对于某些常数 c 和 n0
0 < f(n) < c.g(n) 对于所有 n>n0
然后老师接着举例，
2n2=O(n3)
现在我知道 Big O 给出了函数的上限，但我对函数 f(n) 到底对应于此处的什么感到困惑？它的意义何在？根据我的理解，g(n) 是表示我们要分析的算法的函数，但是 f(n) 或示例 2n2 的目的是什么？
需要对此进行一些说明，我已经被困在这里几个小时了。
f(n) 是为您提供您要测量的事物的确切值的函数（时间、处理器指令数、迭代步骤数、使用的内存量等）。
g(n)是另一个逼近f(n)增长的函数。
在通常情况下，您并不真正了解 f(n) 或者它很难计算。例如，时间取决于处理器速度、内存访问模式、系统负载、编译器优化等。 g(n) 通常非常简单，如果 f(n) = O(N) 更容易理解，如果你将 n 加倍，在最坏的情况下，你将大致加倍运行时间。由于它是上限 g(n) 不一定是最小值，但通常人们会在不必要的情况下尽量避免膨胀它。在您的示例中，O(n^3) 是 2n^2 的上限，但 O(n^2) 和 O(n!) 也是如此。
在大O符号的正式定义中，函数f(n)和g(n)是其他函数的占位符，例如，在二次公式中，字母a、b、和 c 是二次方程中实际系数的占位符。
在你的例子中，讲师讲的是 2n2 = O(n3)。您有一个正式的定义，一般来说，f(n) = O(g(n)) 为真意味着什么。因此，让我们将其与上面的数学进行模式匹配。看起来 f(n) 是左边的东西，g(n) 是右边的东西，所以在这个例子中 f(n) = 2n2 和 g(n ) = n3.
上一段仅通过一个例子就对f(n)和g(n)的含义进行了粗浅的解释，但最好还是谈谈它们的真正含义.在数学上，f(n) 和 g(n) 实际上可以是您喜欢的任何函数，但通常当您在算法分析的上下文中使用大 O 表示法时，您通常会让 f(n)是相关算法完成的真实工作量（或者它的运行时间，或者它的 space 用法，或者实际上只是其他任何东西）并且会选择 g(n) 作为某个 "nice" 函数更容易推理。例如，您正在分析的某些函数可能具有真正的运行时间，作为 n 的函数，如 16n3 - 2n2 - 9n + 137。这就是你的函数 f(n)。由于 big-O 表示法背后的全部要点是能够（在数学上严格且安全地）丢弃常数因子和低阶项，我们将尝试选择以与 f(n) 相同的速率增长的 g(n)但更容易推理 - 例如，g(n) = n3。所以现在我们可以通过看能否找到big的正式定义中提到的常数c和n0来尝试判断f(n) = O(g(n)) -O 表示法。
回顾一下：
- 定义中的f(n)和g(n)只是其他函数的占位符。
- 在实际使用中，f(n) 将是所讨论算法的真实运行时间，而 g(n) 将简单得多，并且以相同的速率增长。
我一直在看麻省理工学院的算法课程讲座，大 O 符号的定义说
f(n) = O(g(n)) 这样对于某些常数 c 和 n0
0 < f(n) < c.g(n) 对于所有 n>n0
然后老师接着举例，
2n2=O(n3)
现在我知道 Big O 给出了函数的上限，但我对函数 f(n) 到底对应于此处的什么感到困惑？它的意义何在？根据我的理解，g(n) 是表示我们要分析的算法的函数，但是 f(n) 或示例 2n2 的目的是什么？
需要对此进行一些说明，我已经被困在这里几个小时了。
f(n) 是为您提供您要测量的事物的确切值的函数（时间、处理器指令数、迭代步骤数、使用的内存量等）。
g(n)是另一个逼近f(n)增长的函数。
在通常情况下，您并不真正了解 f(n) 或者它很难计算。例如，时间取决于处理器速度、内存访问模式、系统负载、编译器优化等。 g(n) 通常非常简单，如果 f(n) = O(N) 更容易理解，如果你将 n 加倍，在最坏的情况下，你将大致加倍运行时间。由于它是上限 g(n) 不一定是最小值，但通常人们会在不必要的情况下尽量避免膨胀它。在您的示例中，O(n^3) 是 2n^2 的上限，但 O(n^2) 和 O(n!) 也是如此。
在大O符号的正式定义中，函数f(n)和g(n)是其他函数的占位符，例如，在二次公式中，字母a、b、和 c 是二次方程中实际系数的占位符。
在你的例子中，讲师讲的是 2n2 = O(n3)。您有一个正式的定义，一般来说，f(n) = O(g(n)) 为真意味着什么。因此，让我们将其与上面的数学进行模式匹配。看起来 f(n) 是左边的东西，g(n) 是右边的东西，所以在这个例子中 f(n) = 2n2 和 g(n ) = n3.
上一段仅通过一个例子就对f(n)和g(n)的含义进行了粗浅的解释，但最好还是谈谈它们的真正含义.在数学上，f(n) 和 g(n) 实际上可以是您喜欢的任何函数，但通常当您在算法分析的上下文中使用大 O 表示法时，您通常会让 f(n)是相关算法完成的真实工作量（或者它的运行时间，或者它的 space 用法，或者实际上只是其他任何东西）并且会选择 g(n) 作为某个 "nice" 函数更容易推理。例如，您正在分析的某些函数可能具有真正的运行时间，作为 n 的函数，如 16n3 - 2n2 - 9n + 137。这就是你的函数 f(n)。由于 big-O 表示法背后的全部要点是能够（在数学上严格且安全地）丢弃常数因子和低阶项，我们将尝试选择以与 f(n) 相同的速率增长的 g(n)但更容易推理 - 例如，g(n) = n3。所以现在我们可以通过看能否找到big的正式定义中提到的常数c和n0来尝试判断f(n) = O(g(n)) -O 表示法。
回顾一下：
- 定义中的f(n)和g(n)只是其他函数的占位符。
- 在实际使用中，f(n) 将是所讨论算法的真实运行时间，而 g(n) 将简单得多，并且以相同的速率增长。