3

请按增长率订购以下功能

n ^ 1.5
n ^ 0.5 + log n
n log ^ 2 n
n log ( n ^ 2 )
n log log n
n ^ 2 + log n
n log n
n

ps：按增长率排序意味着随着n越来越大，最终哪个函数的值会高于其他函数。

ps2。我已经订购了大部分函数：n、n log log n、n log n、n log^2 n、n log (n^2)、n^1.5

我只是不知道如何排序：n ^ 2 + log n，n ^ 0.5 + log n，这2个值

谁能帮我？谢谢

4

7 回答 7

5

您可以通过绘制函数图并查看哪些函数变大来相当容易地解决这个问题（找到一个图形计算器，查看Maxima或尝试在Wolfram Alpha上绘制函数图）。或者，当然，您只需选择一些较大的 n 值并比较各种函数，但图表可以提供更好的画面。

于 2009-10-18T01:34:09.060 回答
3

您寻求答案的关键是，当您将两个函数相加时，它们的组合“增长率”将与两者中增长率较高的一个完全相同。因此，您现在知道这两个函数的增长率，因为您似乎（从知道所有其他函数的正确顺序）知道这里起作用的增长率的正确顺序。

于 2009-10-18T01:33:38.093 回答
3

大量插入不是解决此问题的正确方法！

既然你有增长的顺序，那么你可以使用以下规则http://faculty.ksu.edu.sa/Alsalih/CSC311_10_11_01/3.3_GrowthofFunctionsAndAsymptoticNotations.pdf

于 2011-06-02T19:01:07.910 回答
1

在所有这些情况下，您都在处理本身具有不同增长率的函数对。

考虑到这一点，只有较大的才是真正重要的，因为即使有一个总和，它也会占主导地位。那么在每个函数总和中，哪个是较大的，它与较大列表中的其他函数相比如何？

于 2009-10-18T01:31:50.640 回答
1

如果你需要数学证明，你应该尝试这样的事情。

如果您有两个功能，例如：

f1(n) = n log n
f2(n) = n

当 n 趋于无穷时，您可以简单地找到 f3(n) = f1(n)/f2(n) 的极限。

如果结果为零，则 f2(n) 的增长率大于 f1(n)。

另一方面，如果结果为无穷大，则 f1(n) 的增长率大于 f2(n)。

于 2013-09-02T19:31:24.263 回答
0

n 0.5（或 n 1/2）是 n 的平方根。因此，它的增长速度比 n 2慢。

于 2009-10-18T01:33:23.117 回答
0 
let say n = 4 then we get 
n ^ 2 + log n       = 16.6020599913
n ^ 1.5             =  8
n                   =  4
n log ( n ^ 2 )     =  4.81
n ^ 0.5 + log n     =  2.60205999133
n log n             =  2.4
n log ^ 2 n         = ? 
n log log n         = -0.8
于 2015-10-30T13:42:12.320 回答