随机化快排和决策树-创新互联

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);

 树的高度决定比较的次数，进而决定时间复杂度；

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。