随机化快排和决策树

发布时间:2020-07-09 03:53:26 作者:汇天下豪杰
来源:网络 阅读:2383

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

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

随机化快排和决策树




推荐阅读:
  1. oracle 快排
  2. kNN算法和决策树

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

快排 决策树 随机化

上一篇:初识Maven与nexus,及nexus安装

下一篇:100 个网络基础知识普及

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》