随机化快排和决策树
1、随机化快速排序算法
创新互联专注于淅川企业网站建设,成都响应式网站建设公司,商城网站建设。淅川网站建设公司,为淅川等地区提供建站服务。全流程定制制作，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务
(1)、快速排序的坏处：完全顺序/完全逆序时时间复杂度为：O(n^2)，其余的情况时间复杂度为：O(nlogn),算法的效率与输入顺序有关；
(2)、随机选择主元，好处：其运行时间不依赖于输入序列的顺序，算法的效率与输入的顺序无关；
(3)、最差的情况由随机数产生器决定，随机化快速排序的时间复杂度为：O(nlogn)；
2、比较排序的算法模型
该模型中，只能做的操作：< <= > .......，来决定元素的相对顺序；
局限性：该模型只能用于可以比较大小的数据类型；
总结：比较排序的算法时间复杂度不会小于：O(nlogn);
3、决策树下的排序算法
有3个数
(1)、决策树：一般情况下，有n个元素需要排序，左边的子树说明ai <= aj；右边的子树对应ai > aj；每一个叶子结点表示一种排序结果，最终的结果a1 < a2 < a3......< an；
(2)、因此比较型排序算法都可以被转换成决策树模型的方式；
(3)、n值的决策树，就是把算法中这些比较的所有可能结果分别列出来；决策树指出了所有可能的路线，用决策树分析比较型的算法是很有用的；
对于n个元素的排序， 用决策树可以证明比较型的排序算法的时间复杂度：取决于树的高度，此时叶子节点的个数是n!，树高>=nlog(n);
树的高度决定比较的次数，进而决定时间复杂度；
分享标题：随机化快排和决策树
标题URL：http://scyanting.com/article/jjjhgp.html
