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，运动员跑得跟理论上所能达到的速度相等了。所以人们就不用再研究排序的最快速度了。

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

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

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

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

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

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

是啊，几个版主也来参和参和，复杂度计算在推理算法里面可是核心，学习DL的人这种问题想逃是逃了不的。 我去理论计算机那个板块转了转，好像那里搞复杂度的比较多，那个版块的版主也来参和一下.

看看这个 Complexity of selected DLs by Ulrike Sattler 有视频哦