|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [求助]各位高人再看啊,问几个算法分析的问题!谢谢先~ (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=54611) |
|
-- 作者：fgffggfg -- 发布时间：10/29/2007 10:42:00 PM -- [求助]各位高人再看啊,问几个算法分析的问题!谢谢先~ 有点乱,大家帮帮忙啊谢谢 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)的运行时间. 谁能大概讲讲这里边什么关系啊
|
|
-- 作者：fgffggfg -- 发布时间：10/31/2007 9:48:00 AM -- 第1个和第2个也没人帮忙吗？？ |
|
-- 作者：gulunhua -- 发布时间：10/31/2007 4:04:00 PM -- log(a*b)=log(a)+log(b) 另外log(1)=0
|
|
-- 作者：gulunhua -- 发布时间：10/31/2007 4:11:00 PM -- 我想关于Ω(nlogn)和O(nlogn)，其实表达的是一个意思，只是写法不同而已，前面那个“噢米贾”符号是标准的数学符号，是希腊字母。 还有那个点应该是乘号吧，相当于(n)*(logn)。 |
|
-- 作者：Logician -- 发布时间：10/31/2007 4:38:00 PM -- ft... Ω(nlogn)表示渐进复杂度“不小于”n·logn阶 |
|
-- 作者：Logician -- 发布时间：10/31/2007 4:41:00 PM -- 从上下文看，第一问的“L”貌似是“……”的意思，像是印刷时的问题（某些公式编辑器换了环境后，符号会变乱）。 |
|
-- 作者：fgffggfg -- 发布时间：11/1/2007 8:59:00 AM -- 要是连log的性质都不知道，我就不用考试类。不过还是谢谢gulunhua哈。 老大这么一说，倒真象是……印错了呵呵。 勘误表真的没法相信了，有错上边查不出不说，还非弄出nlog和n.log两种写法，还以为真有区别呢！ |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
70.313ms |