桶排序时间复杂度 桶排序时间复杂度是什么
2020-07-29 天奇生活 【 字体:大 中 小 】
桶排序时间复杂度:O(N+C),其中C=N*(logN-logM)。桶排序是一个排序算法,工作的原理是将数组分到有限数量的桶子里,每个桶子再使用别的排序算法或以递归方式继续使用桶排序进行排序。
桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。此外,桶排序是稳定的。
桶排序的方法
桶排序算法要求,数据的长度必须完全一样,程序过程要产生长度相同的数据,其方法为:Data=rand()/10000+10000。
每次进行下一次的扫描顺序是按照上次扫描的结果来的,所以设计上提供相同的两个桶数据结构。前一个保存每一次扫描的结果供下次调用,另外一个临时拷贝前一次扫描的结果提供给前一个调用。
在桶排序算法的代码中,假设输入是含n个元素的数组A,且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶,并假设可以用某种机制来维护这些表。
猜你喜欢
夏至的民俗农事有哪些风俗 夏至的风俗有哪些
与夏至有关的古诗有哪些 与夏至有关的古诗反映了什么
夏至北半球什么最短什么最长 北半球的昼夜长短是何如变化的
夏至有哪些常吃的食物 夏至的习俗
夏至后如何确定暑伏时间 三伏指的是什么
为什么气温最高不是夏至日 高温天气应当注意什么
夏至太阳直射点向哪移动 什么是太阳直射点
为什么夏至正午太阳最大 夏至后的天气特点
夏至和盛夏有什么区别 什么是夏至
立夏吃羊肉还是夏至吃羊肉 立夏和夏至的饮食习俗
桶排序时间复杂度 桶排序时间复杂度是什么
美股开盘时间 美股什么时候开盘
钱塘江大潮的时间 钱塘江大潮时间是什么时候
泉城广场喷泉时间 济南泉城广场喷泉简介
高铁检票时间 高铁多久开始检票
五四运动时间 五四运动的起因