如何按照增长率的顺序排列函数？所以 f(n) 是 O(g(n))
How to arrange the functions in the order of growth rate? So that f(n) is O(g(n))
我有以下功能需要按增长率排序。但是我们如何证明函数g(n)在列表中紧跟在函数f(n)之后，那么f(n)应该是O(g(n))？
我尝试为 n 输入一些值（例如 10、1000、5000），结果是 5 < 4 < 2 < 1 < 3，从 1000 开始。
如何渐进地证明这个顺序？
任何正多项式函数比任何多对数函数增长得更快，即 lg^b(n) = o(n^a) 对于任何 a > 0 (注意小 o)
这意味着 f2 >> f4。
其他一切（呈指数增长）都比 f2 增长得更快。
比较 f1 = 10^n 和 f3 = n^n
两边取log比较nlog10和nlogn。显然，f3 >> f1（log10 是常数）。
比较 f3 = n^n 和 f5 = 2^(log^1/2(n))
对两边取对数比较nlogn和(log^1/2(n))log2。 f3 >> f5（两边平方，或利用以下事实：任何正多项式函数比任何多项式对数函数增长得更快）
剩下的就是比较f5 = 2^(log^1/2(n))和f1 = 10^n.
两边取log比较(log^1/2(n))log2和nlog10。 f1 >> f5。
利用所有这些事实可以得出结论，f4 << f2 << f5 << f1 << f3。或者，正如其他人指出的那样，您可以通过计算极限来比较它们。
请看下面的回答，因职权用图片发帖。
我有以下功能需要按增长率排序。但是我们如何证明函数g(n)在列表中紧跟在函数f(n)之后，那么f(n)应该是O(g(n))？
我尝试为 n 输入一些值（例如 10、1000、5000），结果是 5 < 4 < 2 < 1 < 3，从 1000 开始。
如何渐进地证明这个顺序？
任何正多项式函数比任何多对数函数增长得更快，即 lg^b(n) = o(n^a) 对于任何 a > 0 (注意小 o)
这意味着 f2 >> f4。
其他一切（呈指数增长）都比 f2 增长得更快。
比较 f1 = 10^n 和 f3 = n^n 两边取log比较nlog10和nlogn。显然，f3 >> f1（log10 是常数）。
比较 f3 = n^n 和 f5 = 2^(log^1/2(n)) 对两边取对数比较nlogn和(log^1/2(n))log2。 f3 >> f5（两边平方，或利用以下事实：任何正多项式函数比任何多项式对数函数增长得更快）
剩下的就是比较f5 = 2^(log^1/2(n))和f1 = 10^n. 两边取log比较(log^1/2(n))log2和nlog10。 f1 >> f5。
利用所有这些事实可以得出结论，f4 << f2 << f5 << f1 << f3。或者，正如其他人指出的那样，您可以通过计算极限来比较它们。
请看下面的回答，因职权用图片发帖。