一个算法复杂度的upper bound 和lower bound是啥
我感觉你应该不是在说算法的upper bound 和lower bound的吧? 而是在问一个问题的upper bound 和lower bound 吧? 一个算法主要的衡量标准是其计算复杂度(如平均复杂度, 最大复杂度什么的)而不是bound, 一个问题的upper bound 通常是指目前现有的解决这一问题的最优的算法(当然并非绝对), 而 lower bound 什么的通常指解决这一类问题至少所需要的复杂度是多少.
举一个简单的例子, 如在量子无序查找的问题中, Grover 算法可以以O(\\sqrt{N})的复杂度(假设N个里面找一个)找到那个解, 是目前最好的算法, 于是在这个问题里的Upper bound就是\\sqrt{N}.
而BBTH98中(当然在此之前好像也有一个结果是基于hybrid method的, 不过我忘了是谁写的了, 好像还在Grover算法之前) 证明了对于任何一个无序的数据集中的查找算法至少需要O(\\sqrt{N})次询问才行,,,,这就说明了这个问题的lower bound是这么多. 另: 这也同时证明了Grover 算法是渐进最优的(紧的).
■网友
lower bound的定义：
An estimate on the minimum amount of work needed to solve a given problem.
【一个算法复杂度的upper bound 和lower bound是啥】 对一个给定的问题，解决这个问题有一个需要的最低运算量，对这个最低运算量的评估，就是lower bound。
■网友
最近也在思考这个lower bound。
我的研究工作是图的编辑距离，通过图的编辑距离来计算俩个图的相似度。上界(upper bound)就是这个图的编辑距离的最多计算的量。
比如给定查询图Q,一个图的数据库D={A,B,C,E}找出编辑距离阈值小于4的所有的图。假设如果没有这个上界和下界，我必须要计算（A,Q） (B,Q) (C,Q) (E,Q)这几组图的编辑距离1,3,5,7；这个时候如果通过分析，计算出一个下界公式(lower bound),数学形式表达为：
，那么对于所有不满足这个下界的
,都不需要要再进行计算，相当于不去考虑哪些表面上压根不符合要求的图。
再举一个形象的例子，给你一堆数据，要你找8在这对数据的位置，如果正确答案是第40个位置，那么给出下界:所有小于等于30的位置的数据不去考虑，你只要去比较30个位置以后的数据就可以了。
大体的意思是上界(upper bound)和下界(lower bound)可以作为一种索引的方法，减小搜索的空间，让计算问题（特别是搜索类的问题）效率更加。
以上是我的理解，数学语言和符合用法不太严谨，如果有什么意见可以和我联系。
■网友
算法哪有lower bound……
推荐阅读
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- 有必要重新开个C店吗
- 大学再有三个月就结束了，没学到知识，参加一个软件测试培训机构好吗
- 汽车|长安UNI-K又将开创一个新的"引力"纪元？
- 神话|武汉传奇父亲：一个平行班孩子创造的高考神话（感动上万家长）
- 王者荣耀李白能不能出肉
- 直播会成为品牌传播的另一个途径么有哪些可行的方法感觉有戏又没头绪好捉急。
- 怎样成为一名合格的Python程序员?
- 知乎有没有必要增加一个特别关注功能