本篇文章给大家谈谈数据结构:排序算法总会提到的上界和下界是什么意思呀，以及输入数字上下界监测算法对应的知识点，文章可能有点长，但是希望大家可以阅读完，增长自己的知识，最重要的是希望对各位有所帮助，可以解决了您的问题，不要忘了收藏本站喔。

本文目录

简单来说，上界就是时间复杂度总不会超过这个数量级，下界就是时间复杂度总不会低于这个数量级。具体去wiki上看下O，Ω，Θ，o，ω的数学定义吧

简单一点，忽略诸如程序在循环变量上的开销，只考虑循环体

复杂度是通过数运算次数直接数出来的，要知道循环多少次，以及每次循环的工作量

(1)循环n次，每次两步加法两步赋值，简单一点讲就是每次循环工作量都是常数，所以复杂度就是Θ(n)（既是上界也是下界）

对于(2)而言，n=n-1下降比较慢，n=n/2下降比较快，同样每次循环的工作量都是常数，只要看循环次数，所以从前者去统计上界，从后者统计下界

最少的情况来自n=2^k的形式，要循环k步，复杂度下界是Ω(log n)

循环次数比较多的情况是反复出现n=n-1运算的情况，但注意一旦执行该运算之后n一定变成偶数，所以最坏情况是n=n-1和n=n/2交替出现，此时循环次数不超过2log_2 n，复杂度上界是O(log n)

合并起来总体的复杂度还是Θ(n)

关于数据结构:排序算法总会提到的上界和下界是什么意思呀到此分享完毕，希望能帮助到您。