您好,登录后才能下订单哦!
1、随机化快速排序算法
(1)、快速排序的坏处:完全顺序/完全逆序时时间复杂度为:O(n^2),其余的情况时间复杂度为:O(nlogn),算法的效率与输入顺序有关;
(2)、随机选择主元,好处:其运行时间不依赖于输入序列的顺序,算法的效率与输入的顺序无关;
(3)、最差的情况由随机数产生器决定,随机化快速排序的时间复杂度为:O(nlogn);
2、比较排序的算法模型
该模型中,只能做的操作:< <= > .......,来决定元素的相对顺序;
局限性:该模型只能用于可以比较大小的数据类型;
总结:比较排序的算法时间复杂度不会小于:O(nlogn);
3、决策树下的排序算法
有3个数<a1, a2, a3>,用决策树进行排序。
(1)、决策树:一般情况下,有n个元素需要排序,左边的子树说明ai <= aj;右边的子树对应ai > aj;每一个叶子结点表示一种排序结果,最终的结果a1 < a2 < a3......< an;
(2)、因此比较型排序算法都可以被转换成决策树模型的方式;
(3)、n值的决策树,就是把算法中这些比较的所有可能结果分别列出来;决策树指出了所有可能的路线,用决策树分析比较型的算法是很有用的;
对于n个元素的排序, 用决策树可以证明比较型的排序算法的时间复杂度:取决于树的高度,此时叶子节点的个数是n!,树高>=nlog(n);
树的高度决定比较的次数,进而决定时间复杂度;
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。