performance - 按效率排序算法

Question

伙计们，我的作业有最后一个问题。问题问：

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。这是正确的吗？

Answer 1

对于n!、n^5、2^n的情况，考虑它们在n+1处是如何增加的，也就是比较(n+1)！到 n!，(n+1)^5 到 n^5，以及 2^(n+1) 到 2^n。

至于您的第一个问题，请按照您认为最有意义的方式进行解释，并确保明确说明这是您对它们的排序方式（对大多数人来说效率最低或相反），以便您的教授知道您的意思。

Answer 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上。

Answer 3

如果可以，请尝试绘制它们。查看图表的外观并比较它们，使用 x 而不是 n。

Answer 4

1. 我会反过来 - 从最有效到最不有效排序，但正如约翰尼评论的那样 - 问教授:)
2. 前 2 个是正确的 - 然后你得到的就被打乱了。

Answer 5

从小到大是什么意思？从最低效率到最高效率？

我会说可能从最高效到最不高效，所以 O(1) -> O(n) -> O(n ² ) 顺序。

鉴于 10,000 是恒定的，我认为这是我最有效的，其次是 nlog(n)，然后是 n!，然后是有效的 n^5，最后是 2^n。这是正确的吗？

这里只是一个提示。用几个 n 值代替其中的每一个，看看哪个增长最快。确保使用相当广泛的值，例如 10 的前 7 或 8 次方。

Answer 6

对于这个作业，只需用大输入代替并进行比较。供您学习.. 有大 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  

从某种意义上说，您现在会发现正确的顺序。