中文XML论坛--[求助]关于复杂度的基本概念的一个问题

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

DL Handbook第三章中提到的Complexity的lower bounds 和 upper bounds分别指什么呢？谢谢！

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

最好和最坏的复杂度

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用pen在2006-3-31 22:59:00的发言：
DL Handbook第三章中提到的Complexity的lower bounds 和 upper bounds分别指什么呢？谢谢！

Complexity的lower bounds 和 upper bounds是一个很专业的词，并不是wason21cn所说的“最好和最坏的复杂度”。不存在“最坏的复杂度”的说法。我在算法中无厘头地加个infinite loop，那么最坏的复杂度就永远是无限了？

lower bounds 所指的是我们理论上所能证明的能达到的最好的复杂度。比如说，100米我们最快要用多长时间？我们能证明人不能快于光速，而光子跑100米需要0.001秒，所以我们可以说lower bound是0.001秒。
upper bound所指的是事实上我们所能达到的最好的复杂度。现在的世界冠军用9.87秒，那么9.87就是upper bound。

算法复杂度的研究就是要提升lower bound，降低upper bound。当它们相等的时候，这个算法问题就完全解决了。还用上面这个例子：我们换个角度来思考lower bound，证明人由于肌肉、血液的限制，起跑的加速度不可能超过100公里2/小时，跑动起来速度不可能超过200公里每小时。所以跑100米至少需要5.34秒。这就是提升“lower bound”。然后训练运动员，不断打破世界纪录，降低upper bound。当一个人跑到理论上所能达到的最快的速度，lower bound=upper bound，我们就再也不用研究跑步问题了。
（以上数字绝对瞎扯，如有类同纯属巧合）

拿具体算法来说：排序。
我们首先有一个lower bound，就是排序的时候起码要把所有数都读一遍，所以lower bound是n。
然后发明冒泡排序，复杂度是n*n。这时候upper bound是n*n
后来，有人发明了Merge Sort，复杂度是nlgn，这时候upper bound是nlgn
那么，有没有可能发明一种算法，复杂度是n呢？
然后，某人从理论上证明，排序的算法至少是nlgn。（具体证明可以找教科书）所以lower bound就是nlgn。
现在，lower bound=upper bound，运动员跑得跟理论上所能达到的速度相等了。所以人们就不用再研究排序的最快速度了。

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

哦，呵呵，原来如此

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

非常感谢BerLin的指点：）

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

感谢BenLin的提示，但是个人对这类问题还是有不同的理解，也希望大家讨论。
首先我这里说的最坏的复杂度，你可以理解为在worst case的情况下。个人理解upper bound是对问题解决的复杂度，即要解决这个问题需要的复杂度，而lower bound是复杂度理论的证明，可以理解为最佳的复杂度。首先我们在这里讨论的关于复杂度研究的问题，有一个很大的前提就是我们研究的问题都是decidable的问题，如果像benlin所说的，算法中有一个infinite loop，这类问题十有八九都是undecidable，根本谈不上复杂度。比如在ALCN的ABox的正确性证明中，一开始给出的算法就不能保证它永远termination，所以我们才修改了原来的算法，在先保证能够termination的前提下，才得到一个复杂度为double exponential的tableau算法。
同意 ‘ lower bounds 所指的是我们理论上所能证明的能达到的最好的复杂度。’ 但是upper bound我还是觉得应该是解决问题至少需要的复杂度，因为在DL中很多问题都是decidable的，所以研究upper bound的问题通常我们是不感兴趣的，我们感兴趣的是lower bound，即最佳复杂度是什么。
我不知道benlin所说的 ‘ 算法复杂度的研究就是要提升lower bound，降低upper bound。当它们相等的时候，这个算法问题就完全解决了 ’ 这个说法来自那里，请赐教，但是根据我跟人学习DL的经验，在DL复杂度的研究主要就是要找出最佳复杂度？什么叫最佳？
给出两个关键字（hardness 和complete），我们说一个问题是hardness的也就是说这个问题是在这类问题中最难的（解决这个最难问题的复杂度），比如很经典的QBF（quantified boolean formula）的valid问题就是一个PSpace－hard的问题，因为它是一个Pspace－hard问题而且是PSpace的问题，所以它是PSpace complete。回到前面的ALCN的Abox正确性问题，我们可以把他的正确性问题转换到QBF这个问题，因为QBF的问题是PSpace complete了，所以说ALCN的Abox的正确性问题的最佳算法就是PSpace。所以lower bound就是 PSpace。
所以对于一个问题解决的算法复杂度来说，要解决这个问题至少需要的复杂度可以理解为upper bound，要优化这个问题使其算法最好而且这个算法不能更好了就是lower bound。

[此贴子已经被作者于2006-4-3 17:58:04编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

wason: 你后面那部分我有点看不懂。
先说前面：
1，当然，我所说的算法复杂度都是worse case。如果不考虑worse case，排序的时候恰巧原始数据就已经排好序，这时候考虑排序的复杂度就没有意义了。
2，对，所讨论的是decidable的问题，也就是P空间的问题。NP的问题不在这次讨论之列。
3，我不知道你所说的“ALCN的ABox”是什么问题，也不知道“很经典的QBF（quantified boolean formula）的valid问题”，恕我孤陋寡闻。
4，好像我没见过P-hard的说法，请指点？我所理解的NP-Complete是指NP空间最难的问题，而NP-Hard是指最难的问题，甚至不能证明这个问题在NP空间中。也就是说，NP-Hard问题包括NP-Complete问题和在NP空间外的难问题。如上所说，这些是NP问题，不在讨论之列。
5，重复一下，Lower bound是理论上解决这个问题至少需要的复杂度。我们目前（可能）还没有这个复杂度的算法，但是我们能证明未来一万年之内设计出来的算法都不可能超过这个复杂度。就比如说爱因斯坦说，人跑步不可能超过光速。
6，解决一个特定问题至少需要的复杂度当然是一个恒定的值。提升lower bound的意思就是用各种理论方法去寻找这个值。用光速理论来考虑人的跑步问题，距离真正人所能跑的速度太远了，所以要想别的方法来证明“跑100米最少需要的时间”，比如说人体动力学，这样来提升lower bound。
7，因为3，所以我没理解你所说的“ALCN的Abox的正确性问题的最佳算法就是PSpace”。这个PSpace是相对应于NP的P空间吗？

以上我所说的这些都是指计算机科学中算法的复杂度研究，并不是专门对DL所说的。其实我没有看LZ所提到的DL Handbook第三章

7，“根据我跟人学习DL的经验，在DL复杂度的研究主要就是要找出最佳复杂度”。我感觉这里所说的复杂度并不是算法复杂度，而是一种compromise的度，让DL既不要太广，也不要太深。不知道这个理解对不对。

8，诸多疑问，但是我基本上同意你的最后一句话：

所以对于一个问题解决的算法复杂度来说，要解决这个问题至少需要的复杂度可以理解为upper bound，要优化这个问题使其算法最好而且这个算法不能更好了就是lower bound。

唯一想要修改的就是把它改成：
所以对于一个问题解决的算法复杂度来说，当前要解决这个问题至少需要的复杂度可以理解为upper bound，而且这个算法不能更好了就是lower bound。
着重提示当前，是说我们可以研究更新的方法来降低算法复杂度，而历史在前进。
删掉“要优化这个问题使其算法最好”，是因为我不理解你这句话的意思。

9，希望更多的人来参与讨论。这个问题基本上是Computer Science人人都能碰到的问题 :)

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

上面说的一大堆，在DL的complexity的研究当中，我觉得最值得研究的就是寻找lower bound，很多关于DL的文章当说到复杂度的时候，如果说是什么complete了，那就是说这个问题的最佳的复杂度就是它了。至于说怎么证明complete，有兴趣可以继续讨论。 Benlin关于你说的复杂度研究问题，我有一个疑惑，我们选择算法的时候，单从经济效率来看，当然是效率越高越好，为什么你还要把lower bound提升呢？你看的关于complexity的书是哪方面的，我看的是computational complexity by Christos H Papadimitriou.

[此贴子已经被作者于2006-4-4 5:41:49编辑过]

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

Admin 也在看着这个帖子，不参和两句？


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	93.750ms