本篇文章给大家谈谈数据结构:排序算法总会提到的上界和下界是什么意思呀，以及输入数字上下界监测算法对应的知识点，文章可能有点长，但是希望大家可以阅读完，增长自己的知识，最重要的是希望对各位有所帮助，可以解决了您的问题，不要忘了收藏本站喔。
本文目录
数据结构:排序算法总会提到的上界和下界是什么意思呀怎么求算法的时间复杂性的上界和下界数据结构:排序算法总会提到的上界和下界是什么意思呀简单来说，上界就是时间复杂度总不会超过这个数量级，下界就是时间复杂度总不会低于这个数量级。具体去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)
关于数据结构:排序算法总会提到的上界和下界是什么意思呀到此分享完毕，希望能帮助到您。