渐近符号图的解释
Explanation for asymptotic notation graph
我目前正在学习算法课程并且遇到了以下图表
我很难理解 f(n) 代表什么，g(n) 是什么意思以及 c和n0的意思。此外，我想知道它们与边界概念的关系及其含义。
大多数教程只是从解释上述术语的相关性开始，而不是解释它们的含义
假设您编写了一个程序来对列表进行排序。您的程序输入一个列表，执行一段时间的计算，然后输出一个排序列表。
“big-O”符号 f(n) = O(g(n)) 是一种比较两个函数 f 和 g 的方法。
在处理数字时，你习惯于进行比较，瞬间“x < y”。
在处理函数时，我们有几种不同的比较方式。例如，您可以说“函数 f 总是小于函数 g”，您可以正式地写成：“forall n, f(n) < g(n)”。
不过，这种比较有点极端。在您问题中显示的图表上，紫色函数并不总是小于蓝色函数。但是您会注意到它仅在 n 的几个小值时更大。所以说“在几个初始值之后，函数 f 最终变得小于函数 cg”或形式上“存在一个数 n0 使得对于所有 n > n0，f(n) < cg(n)”是有意义的。
现在，我们原本要比较的函数是f和g，而不是f和cg。但是，也许我们不关心乘法常数；也许我们只关心当 n 增加时 f(n) 的行为，以及当 n 增加时 g(n) 的行为。例如，您可能注意到当 n 增大 10 倍时，f(n) 大约增大 100 倍。这意味着 f(n) 大致与 n^2 成正比。 f 大约等于 n^2 + 5 还是 7 * n^2 + 2 * n + 12 对我们来说并不重要。对我们来说重要的是它大致与 n^2.[=18= 成正比]
因此 Big-O 符号为我们提供了一种方法来比较两个函数 f(n) 和 g(n)，同时忽略乘法常数，并忽略 f(n) 和 g(n) 的小值共
f(n) = O(g(n)) 字面上的意思是“存在一个值 n0 和一个乘法常数 c，只要 n 大于 n0，f(n) 就会小于 c g(n).
这个定义与算法的复杂度分析有关。假设您编写了一个算法来对列表进行排序。我们将 f(n) 称为您的算法对 n 项列表进行排序所需的最大操作数。你想证明你的算法是有效的。你想做诸如“f(n) = O(n^2)”之类的语句，这大致意味着“如果列表的大小乘以 10，那么执行时间将乘以小于 100” .这并没有给出 exact 的操作次数——可能是 f(n) = 4 n^2，或者 f(n) = (n^2 - n) / 2。但是谁在乎确切的数字。重要的是，如果列表长10倍，执行的时间最多长100倍。
我目前正在学习算法课程并且遇到了以下图表
我很难理解 f(n) 代表什么，g(n) 是什么意思以及 c和n0的意思。此外，我想知道它们与边界概念的关系及其含义。
大多数教程只是从解释上述术语的相关性开始，而不是解释它们的含义
假设您编写了一个程序来对列表进行排序。您的程序输入一个列表，执行一段时间的计算，然后输出一个排序列表。
“big-O”符号 f(n) = O(g(n)) 是一种比较两个函数 f 和 g 的方法。
在处理数字时，你习惯于进行比较，瞬间“x < y”。
在处理函数时，我们有几种不同的比较方式。例如，您可以说“函数 f 总是小于函数 g”，您可以正式地写成：“forall n, f(n) < g(n)”。
不过，这种比较有点极端。在您问题中显示的图表上，紫色函数并不总是小于蓝色函数。但是您会注意到它仅在 n 的几个小值时更大。所以说“在几个初始值之后，函数 f 最终变得小于函数 cg”或形式上“存在一个数 n0 使得对于所有 n > n0，f(n) < cg(n)”是有意义的。
现在，我们原本要比较的函数是f和g，而不是f和cg。但是，也许我们不关心乘法常数；也许我们只关心当 n 增加时 f(n) 的行为，以及当 n 增加时 g(n) 的行为。例如，您可能注意到当 n 增大 10 倍时，f(n) 大约增大 100 倍。这意味着 f(n) 大致与 n^2 成正比。 f 大约等于 n^2 + 5 还是 7 * n^2 + 2 * n + 12 对我们来说并不重要。对我们来说重要的是它大致与 n^2.[=18= 成正比]
因此 Big-O 符号为我们提供了一种方法来比较两个函数 f(n) 和 g(n)，同时忽略乘法常数，并忽略 f(n) 和 g(n) 的小值共
f(n) = O(g(n)) 字面上的意思是“存在一个值 n0 和一个乘法常数 c，只要 n 大于 n0，f(n) 就会小于 c g(n).
这个定义与算法的复杂度分析有关。假设您编写了一个算法来对列表进行排序。我们将 f(n) 称为您的算法对 n 项列表进行排序所需的最大操作数。你想证明你的算法是有效的。你想做诸如“f(n) = O(n^2)”之类的语句，这大致意味着“如果列表的大小乘以 10，那么执行时间将乘以小于 100” .这并没有给出 exact 的操作次数——可能是 f(n) = 4 n^2，或者 f(n) = (n^2 - n) / 2。但是谁在乎确切的数字。重要的是，如果列表长10倍，执行的时间最多长100倍。