楼主

[求助]各位高人再看啊,问几个算法分析的问题!谢谢先~ 有点乱,大家帮帮忙啊谢谢           1.北大教材p248:      log(n!)=log(n*(n-1)*(n-2)*L*2*1)      log(n!)=logn+log(n-1)+log(n-2)+L+log2+log1      log(n!)>=logn+log(n-1)+log(n-2)+L+log(n/2)      问下这个L是指什么,怎么能logL=L呢??      还有2式到3式是怎么来的啊? 2.问下算法分析中Ω(nlogn)和O(nlogn)区别在哪,教材上并没教Ω的 还有看教材勘误里有O(nlogn)和Θ(n.logn),问下中间的.点怎么回事? 3.p249开头有一段"绕口令"(把我读迷糊了):     既然所有基于比较的排序算法都需要Ω(nlogn)的时间开销,那么排序问题本身需要的运行时间也是Ω(nlogn).已经知道所有排序算法都需要O(nlogn)的运行时间,因此可以推导出排序问题需要Θ(nlogn)的运行时间.     谁能大概讲讲这里边什么关系啊    收藏   分享   顶(0)    关闭广告显示

	第2楼

第1个和第2个也没人帮忙吗？？

	第3楼

log(a*b)=log(a)+log(b) 另外log(1)=0

----------------------------------------------
努力进取

	第4楼

我想关于Ω(nlogn)和O(nlogn)，其实表达的是一个意思，只是写法不同而已，前面那个“噢米贾”符号是标准的数学符号，是希腊字母。 还有那个点应该是乘号吧，相当于(n)*(logn)。

----------------------------------------------
努力进取

	第5楼

ft... Ω(nlogn)表示渐进复杂度“不小于”n·logn阶 O(nlogn)表示渐进复杂度“不大于”n·logn阶 两个正好是反的。 相应的还有（注意大小写）： ω(f(n))表示渐进复杂度“大于”f(n)阶 o(f(n))表示渐进复杂度“小于”f(n)阶 Θ(f(n))表示渐进复杂度“等于”f(n)阶

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	第6楼

从上下文看，第一问的“L”貌似是“……”的意思，像是印刷时的问题（某些公式编辑器换了环境后，符号会变乱）。

----------------------------------------------
Three passions, simple but overwhelmingly strong, 
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

	第7楼

要是连log的性质都不知道，我就不用考试类。不过还是谢谢gulunhua哈。 老大这么一说，倒真象是……印错了呵呵。 勘误表真的没法相信了，有错上边查不出不说，还非弄出nlog和n.log两种写法，还以为真有区别呢！