决策树和桶排序

作者: Sun东辉 | 来源:发表于2022-05-13 08:23 被阅读0次

决策树和桶排序
算法基础排序(一)
桶排序和计数排序
浅谈排序算法
《数据结构与算法之美》10——排序（三）桶排序、计数排序、基数排
桶排序
2021-03-08 排序算法之桶排序
桶排序，计数排序和基数排序
桶排序与哈希桶排序
php-计数排序、基数排序、桶排序

决策树

决策树（decision tree）是用于证明下界的抽象概念。每个节点表示在元素之间一组可能的排序，它与已经进行的比较一致。比较的结果是树的边。

只是用比较进行排序的每一种算法都可以用决策树表示。当然，只有输入数据非常少的情况下画决策树才是可行的。排序算法所使用的比较次数等于最深的树叶的深度。所使用的比较的平均次数等于树叶的平均深度。由于决策树很大，因此必然存在一些长的路径。

引理 1：令 T 是深度为 d 的二叉树，则 T 最多有 $2^d$ 片树叶。

引理 2：具有 L 片树叶的二叉树的深度至少是 $\log L$ 。

引理 3：只使用元素间比较的任何排序算法在最坏情形下至少需要 $\log(N!)$ 次比较。

引理 4：只使用元素间比较的任何排序算法需要进行 $`\Omega(N log N)`$ 次比较。

桶排序

为使桶排序能够正常工作，必须要有一些额外的信息。输入数据 $A_1,A_2,...,A_N$ 必须只由小于 M 的正整数组成。（显然还可以对其进行扩充。）如果是这种情况，那么算法很简单：使用一个大小为 M 称为 Count 的数组，它被初始化为全 0。于是，Count 有 M 个单元（或称桶），这些桶初始化为空。当读 $A_i$ 时， $Count[A_i]$ 增 1。在所有的输入数据读入后，扫描数组 Count，打印除排序后的表。该算法用时 $O(M+N)$ 。