我一直在看麻省理工学院的算法课程和大O符号的定义
f（n）=o（g（n））因此对于某些常数c和n0
0n0
然后老师接着举了一个例子，
2n2=O（n3）
现在我得到了大O给出了函数的上界，但是我很困惑，函数f（n）到底对应于什么它的意义是什么？根据我的理解，g（n）是表示我们试图分析的算法的函数，但是f（n）的目的是什么，或者如示例2n2所示？
需要澄清一下，我已经在这里呆了好几个小时了。
最佳答案
在big-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）确实可以是任何你想用的函数，但通常当你在算法分析的上下文中使用big-o符号时，你通常会让f（n）成为问题算法（或其运行时，或其空间使用，或者真的是其他任何东西）并且会选择g（n）作为一些更容易推理的“好”函数。例如，您正在分析的某个函数可能有一个真正的运行时，作为n的函数，如16n3-2n2-9n+137这就是你的函数f（n）。由于big-o符号背后的整个点是能够（数学上严格和安全地）丢弃常数因子和低阶项，我们将尝试选择一个g（n），它的增长速度与f（n）相同，但更容易推理，比如g（n）=n3。所以现在我们可以试着确定f（n）=o（g（n））了，看看我们能否找到big-o符号的形式定义中提到的常数c和n0。
概括一下：
定义中的f（n）和g（n）只是其他函数的占位符。
在实际应用中，f（n）将是所讨论算法的真正运行时，g（n）将是以相同速度增长的更简单的东西。