algorithm - 大 O 表示法 : Definition

Question

我一直在看麻省理工学院的算法类(class)讲座，大 O 符号的定义说 f(n) = O(g(n)) 这样对于某些常量 c 和 n₀
0 < f(n) < c.g(n) 对于所有 n>n₀

然后导师接着举例，
2n²=O(n³)

现在我知道 Big O 给出了函数的上限，但我对函数 f(n) 到底对应于此处的什么感到困惑？它的意义何在？根据我的理解，g(n) 是表示我们要分析的算法的函数，但是 f(n) 或示例 2n² 中的目的是什么？

需要对此进行一些澄清，我已经被困在这里几个小时了。

Answer 1

在大 O 表示法的正式定义中，函数 f(n) 和 g(n) 是其他函数的占位符，例如，在二次公式中，字母 a、b 和 c是二次方程中实际系数的占位符。

在您的示例中，讲师正在谈论 2n² = O(n³)。您有一个正式的定义，一般来说，f(n) = O(g(n)) 为真意味着什么。因此，让我们将其与上面的数学进行模式匹配。看起来 f(n) 是左边的东西，g(n) 是右边的东西，所以在这个例子中 f(n) = 2n² 和 g(n) = n ³.

上一段仅通过一个示例对 f(n) 和 g(n) 的含义进行了粗略的解释，但最好谈谈它们的真正含义。。在数学上，f(n) 和 g(n) 实际上可以是您喜欢的任何函数，但通常当您在算法分析的上下文中使用大 O 表示法时，您通常会让 f(n)是所讨论算法完成的真实工作量(或其运行时间、空间使用量或其他任何东西)，并将选择 g(n) 作为一些更容易推理的“好”函数。例如，您正在分析的某些函数可能具有真正的运行时间，作为 n 的函数，如 16n³ - 2n² - 9n + 137 . 那就是你的函数 f(n)。由于 big-O 表示法背后的全部要点是能够(在数学上严格且安全地)丢弃常数因子和低阶项，我们将尝试选择以与 f(n) 相同的速率增长的 g(n)但更容易推理 - 例如，g(n) = n³。所以现在我们可以通过看能否找到big-O记法形式化定义中提到的常量c和n₀来判断是否f(n) = O(g(n)) .

总结一下:

• 定义中的f(n)和g(n)只是其他函数的占位符。
• 在实际使用中，f(n) 将是所讨论算法的真实运行时间，而 g(n) 将简单得多，但会以相同的速率增长。