伙计们，我的作业有最后一个问题。问题问：
Reorder the following efficiencies from smallest to largest:
2^n
n!
n^5
10,000
nlog(n)
再次..请不要直接回答这个问题。
我的问题：
1.) 从最小到最大是什么意思？从最低效率到最高效率？
2.) 鉴于 10,000 是恒定的，我认为这是我最有效的，其次是 nlog(n)，然后是 n!，然后是有效的 n^5，最后是 2^n。这是正确的吗？
问问题
401 次
6 回答
3
对于n!、n^5、2^n的情况，考虑它们在n+1处是如何增加的，也就是比较(n+1)！到 n!，(n+1)^5 到 n^5，以及 2^(n+1) 到 2^n。
至于您的第一个问题，请按照您认为最有意义的方式进行解释，并确保明确说明这是您对它们的排序方式（对大多数人来说效率最低或相反），以便您的教授知道您的意思。
于 2013-01-23T17:34:52.137 回答
2
f(n) = O(g(n))意味着对于某些常数和足够大的 ，|f(n)|总是小于或等于。这意味着您将函数值与无穷大进行比较。c * |g(n)|cnn
例如100 * n小于n²小n，但从n = 100上开始n²总是大于或等于100 n，因此被认为是“更大”。
它不能反过来工作——无论你选择多大的常数c，总会有一些n0这样的n > n0 n² > c * 100 * n。如果您例如选择c = 1,000,000 n²仍然大于或等于c * 100 * n从n = 100,000,000上。
于 2013-01-23T17:34:32.693 回答
1
如果可以，请尝试绘制它们。查看图表的外观并比较它们，使用 x 而不是 n。
于 2013-01-23T19:25:54.643 回答
0
- 我会反过来 - 从最有效到最不有效排序，但正如约翰尼评论的那样 - 问教授:)
- 前 2 个是正确的 - 然后你得到的就被打乱了。
于 2013-01-23T17:29:47.410 回答
0
从小到大是什么意思？从最低效率到最高效率？
我会说可能从最高效到最不高效，所以 O(1) -> O(n) -> O(n 2 ) 顺序。
鉴于 10,000 是恒定的，我认为这是我最有效的，其次是 nlog(n)，然后是 n!，然后是有效的 n^5，最后是 2^n。这是正确的吗？
这里只是一个提示。用几个 n 值代替其中的每一个，看看哪个增长最快。确保使用相当广泛的值，例如 10 的前 7 或 8 次方。
于 2013-01-23T17:30:08.607 回答
0
对于这个作业，只需用大输入代替并进行比较。供您学习.. 有大 O ，欧米茄符号和 Theta Θ。
Big O 是你应该为这个作业得到的，因为这是你的函数永远不会超过的上限，.. 在大值中。
Omega Ω 是下限，这是函数永远不会低于小值的下限。以 1,000,000 为例。
Theta Θ介于两者之间。
但在现实生活中，我总是只面对大 O 符号。
let n = 1000
2^n =~ 1e30
n! =~ too BIG!
n^5 =~ 1e15
10,000 =~ 10000
nlog(n) 3000
从某种意义上说，您现在会发现正确的顺序。
于 2013-01-23T18:18:35.190 回答