排序时间复杂度

鉴于以下列表的复杂性：排序时间复杂度

n^(log log(n)) ;2^n ;3^n ;n! ; n^3 ;1/n ;(n+1)! ; 4^log(n) ;n^2 

n^log(n) ;log(n!) ;nln(n) ; log(2^n)=nlog2 ;(log(2))^n ;5n^2+6 ; n^log(n!)

我需要通过类来对它们进行排序。

我整理由下列顺序其中的一部分，但我仍然缺少一些：

(n+1)! 
n! 
3^n 
2^n 
(3/2)^n 
(log(n))^log(n) =n^log(log(n)) 
n^3 
n^2 = 4*log(n) = 4^log(n) 
5n^2+6 = Θ(n^2) 
log(n!) = Θ(n*log(n)) 
nlog(2) = log(2^n)

我在哪里需要把休息：

n^log(n) ; n*ln(n) ; (log(2))^n ; n^[log(n!)] ; 1/n ;

？

而且，我怎样才能将它们分为普通类？

我想感谢所有帮助

问候

来源

2012-03-27 ron

这是功课吗？ – Shahbaz 2012-03-27 15:43:32

题外话：这可能应该在http://cs.stackexchange.com上。 – 2012-03-27 15:44:02

我不能告诉你如何回答这个作为一个家庭作业的问题。这可能取决于你的教练想要什么。然而，虽然计算机科学令人遗憾地经常不能识别它，但是！是无限阶的，log（n）是零阶。 L'医院的规则管辖。（我真的不认为这会对你的作业有所帮助，因为这个问题的措辞表明你的教师不同意这个评论的前提。） – thb 2012-03-27 15:48:40

你迄今做得很好。由于这是一门功课，我不会给一个确切的答案，但只有约提示你缺少的：

n^log(n)：这个增长速度比(log(n))^(log(n))快，但速度不及指数。您可以通过将这三个表达式的log s进行比较来确认这一点。
n*ln(n)：ln(n)是ln(10)log(n)。一般来说，记录一个基数c，记录一个基数b乘以基数c中的log b。
(log(2))^n：这是一个指数，基数为log(2)，它是〜0.3。这几乎（3.333^-n）呈指数下降。
n^[log(n!)]：log(n!)是O(nlog(n))。这意味着n^(log(n!))是O(n^n * n^log(n))
1/n：这是n^(-1)其通过值慢慢减小。

来源

2012-03-27 15:56:59 Shahbaz

我已经回答了我的问题，非常感谢，如果你能给我一个反馈... :) – ron 2012-03-27 17:12:04

我最后的答案：

n^log(n!) 
(n+1)! 
n! 
3^n 
2^n 
(3/2)^n 
n^log(n) 
(log(n))^log(n) =n^log(log(n)) 
n^3 
n^2=4 log(n)=4^log(n) 
5n^2+6=Θ(n^2) 
log(n!)=Θ(nlog(n)) 
n⋅ln(n) 
nlog(2)=log(2^n) 
(log(2))^n≈(0.3)^n 
1/n=n^(-1)

你觉得呢？

来源

2012-03-27 16:54:34 ron

'4 ^（log（n））'是'n ^（log（4））'这将是'n^2'如果你的日志是基数2，但你是如何得到'4 * log（n）'等于那些？！另外，如果你的日志是基数2，那么'log（2）'将是1，所以'log（2）^ n'将会是简单的1. – Shahbaz 2012-03-27 17:14:23

非常感谢！ – ron 2012-03-27 17:29:25

排序时间复杂度

回答

相关问题