Day-12 决策树(decision tree)

排序的速度

Quicksort，需要
heapsort，需要
merge sort，需要
insertion sort，需要

在前几天的时间我们看到了这一些演算法，我们发现他们最快时间都在，那有没有可能有一个演算法它的速度是快过於的?

我们会发现这上面四种排序的演算法都有一个性质，就是透过比较两个元素的大小关系来做出排序，也就是它们是基於同样的一种演算法模型去设计的演算法，而在这个演算法模型底下，是我们能够达到的最快速度。

比较排序的演算法模型，决策树

在这个演算法模型中，规范了我们能够对两个元素a和b进行怎样的操作，像是我们可以执行, , , , 这些操作，如果我们对整数集合进行排序，我们只能对元素进行比较的操作，不能做出相加，相乘等等在这个演算法模型规范以外的操作。

关於透过比较方式进行的排序，我们可以使用决策树来表示他，决策树是一颗完全二元树，他可以表示给定固定大小的输入，产生出所有可能排序情况。

假设给定阵列

从树根开始看，比较和，
如果，就和进行比较。
如果，就和进行比较。

给定阵列，我们想要产生出由小到大的排列，整个决策树的走法如下

最终产生出的组合为(3,1,2)，即为由小到大的排列方式。

在决策树中，每一个内部节点都是以标记，其中，维阵列中元素的个数。每个内部节点会分出两颗子树，左子树表示所需要进行的後续比较，右子树表示所需要进行的後续比较。对於一个正确的比较排序演算法，个元素的阵列会产生出种排列的情况，也就是产生出个叶节点。

上面提及的四种演算法都可以使用决策树的方式进行表示，但一般来说不会那麽做，原因为考虑一般性，也就是考虑排序长度为的阵列，会有个节点，导致树长的非常大一棵，因此一般描述演算法时会采用虚拟码的方式进行描述。

使用决策树的好处，在於我们可以直观的分析对於长度为的阵列，排序所需要的执行时间与最差情况。

执行时间与最差情况

从树根到任一叶节点之间的路径长度，表示排序演算法所需要进行比较的次数，也就是执行时间，可以表示成树的深度。而最坏情况就是树根到叶节点最长的路径长度，也就是树的高度，有最多的比较次数。

我们要证明在这个比较模型底下，没有任何一种演算法是要比还要快的，也就是最长路径的最小值为

证明: 对於长度为n的阵列所绘制出的决策树，其树高为
对於长度为n的阵列所绘制出的决策树，其拥有个节点，令决策树的高度为，叶子数量为，则最多拥有个叶节点，因为这是一棵二元树，每个节点都有两个分支，因此我们可以得出下面关系式
，对两边式子取对数
(因为为单调递增函数，因此可以做这样的操作)
根据Stirling's formula，用来取的近似值


，和为常数，当n趋近於无限时可以忽略不计

结论: 对於使用比较大小方式进行排序的演算法，皆可以对应到决策树，并且效率都不会好过於，而heapsort,merge sort和随机化的quicksort他们执行时间的上界为，恰好对应到决策树的下界。随着n的增长，heapsort,merge sort随机化的quicksort会渐进式的趋近於在决策树模型下的最优解，也就是贴近他的下界。

突破模型的限制，线性时间的排序法

线性时间几乎是我们可以得到的最有效率结果(不考虑平行化处理或是一些情况)，因为我们至少需要遍历过整个数据。

如何在线性时间内完成排序，要突破模型的限制，就是我们不在比较元素的大小，对元素做其他的操作，也就是让这个演算法不被这个模型所包含，那这个演算法就有机会达到线性时间内的排序了。

参考资料:Introduction to algorithms 3rd