Day-18 BFPRT演算法

最坏情况为 $\Theta(n)$ ，BFPRT演算法

在由随机数决定阵列的分割的情况下，我们如何避免产生出最差情况(虽然出现的机率很小)，或是让最差的情况时间复杂度也是 $\Theta (n)$ 。

BFPRT演算法(由 Blum, Floyd, Pratt, Rivest 与 Tarjan 创造)可以实现出这一件事情，这是一个具有确定性(deterministic)的演算法，也就是不含任何随机的成分。

我们会产生出最差的情况为分割极度不平衡，也就是产生出 $0:n-1$ 这种分割，而会产生出这种分割，和我们的主元(pivot)的选择很有关系，如果我们可以保证选择到的主元(pivot)都是好的，确保不会产生出最差分割，这个主元是确定是最好的，也就是在样本空间无限大时，每一次的主元都是好的，而不是机率上趋近於最好。那麽这个演算法就可以避免掉最差情况的发生。而这就是BFPRT演算法的主要想法。

BFPRT演算法遵循以下五个步骤

将n个元素的 $A$ 阵列(不一定要是阵列)拆分成 ${\lfloor}n/5{\rfloor}$ 组，每一组含有5个元素，最後一组由 $n\ {mod}\ 5$ 组成，如果 $n=1$ ，则直接回传 $A[n]$ 。
寻找这 ${\lceil}n/5{\rceil}$ 组中每一组的中位数，方法为对每一组元素使用insertion sort，排序後找出中位数，每一组都有五个元素，因此经过排序後地三个元素即为中位数。
在2.中会找出 ${\lceil}n/5{\rceil}$ 个中位数，把这些中位数也组成一个阵列，在这个阵列中找到中位数 $x$ (透过递回呼叫BFPRT)。
在3.产生出由中位数产生的阵列，以 $x$ 作为主元(pivot)对阵列进行划分。比 $x$ 小的元素划分到 $x$ 的左边， $x$ 本身被划分到左边，而比 $x$ 大的元素划分到左边。
将 $k$ 定义为 $k = rank(x)$ ，也就是将 $k$ 当作 $x$ 在阵列中大小的排名，而输入的参数 $i$ 表示我们要寻找阵列中第 $i$ 大的元素。
如果 $i=k$ ，则直接回传 $x$ 。
如果 $i < k$ ，则在阵列中左分割的部分，也就是比 $x$ 小的部分递回呼叫BFPRT
如果 $i > k$ ，则在阵列中右分割的部分，也就是比 $x$ 大的部分递回呼叫BFPRT

范例 : 输入一个有34个元素的A阵列， $A[34]$

将n个元素的 $A$ 阵列拆分成 ${\lfloor}n/5{\rfloor}$ 组，每一组含有 $5$ 个元素，最後一组由 $n\ {mod}\ 5$ 个元素组成。
寻找这 ${\lceil}n/5{\rceil}=7$ 组中每一组的中位数
在2.中会找出 ${\lceil}n/5{\rceil}=8$ 个中位数，把这些中位数也组成一个阵列，在这个阵列中找到中位数 $x$ (透过递回呼叫BFPRT)。
在3.产生出由中位数产生的阵列，以 $x$ 作为主元(pivot)对阵列进行划分。比 $x$ 小的元素划分到 $x$ 的左边， $x$ 本身被划分到左边，而比 $x$ 大的元素划分到左边。

$x$ 的排名为第3名，令 $k=rank(x)$ ，中位数组成的子阵列有7个元素， $n=7$ ，右边的分割有 $n-k=4$ 个元素，左边分割有 $n-k-1=3$ 个元素
接着通过递回呼叫找到我们要的元素

我们把上面这个阵列看作是一张图(graph)，我们在两个节点(或是元素)定义以下符号，表示 $a < b$

我们把这样的符号，加到上面的图上

我们也对中位数构成的子阵列加上这样的符号

得到这张非常混乱，~~就像是我的面包版的图~~

我们使用箭头，表示是一个有向路径，也就是我们走访的路线，我们可以透过任一条路径，得知两个元素之间的大小关系，且通过这个路径，我们可以知道阵列每一个区块和 $x$ 之间的关系。

由箭头我们可以知道 $a < b$ ， $b < x$ ，因此 $a < x$ ， $a$ 上面的元素也必定小於 $x$ ，旁边的分组也是如此，因此我们可以知道，灰色区域框住的阵列区块中所有元素皆小於等於 $x$

而橘色部分中所有元素，必定大於等於 $x$

由上面这张图我们可以知道，每一个分组中有 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 的元素会小於等於 $x$ ，而我们将这个含有 $34$ 个元素的阵列拆分成 ${\lfloor}n/5{\rfloor}+1$ 组( $+1$ 为含 $n \ mod\ 5$ 个元素的组)，其中有 ${\lfloor}{\lfloor}n/5{\rfloor}/2{\rfloor}$ 的组会存在 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 的元素会小於等於 $x$ 这个性质，因此，我们可以推导出以下性质:

给定 $n$ 个元素的 $A$ 阵列 :

$3{\lfloor}{\lfloor}n/5{\rfloor}/2{\rfloor}$ 个元素小於等於 $x$ ，(在由中位数划分出的子阵列中，有 ${\lfloor}n/5{\rfloor}/2$ 个元素小於等於 $x$ )

而每一个分组中，也至少会有 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 个元素大於等於 $x$ ，而我们将含有 $34$ 个元素的阵列猜分成 ${\lfloor}n/5{\rfloor}=6+1$ 组，其中有 ${\lfloor}{\lfloor}n/5{\rfloor}/2{\rfloor}+2$ 会具有 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%203%205$ 的元素大於等於 $x$ 这个性质，

给定 $n$ 个元素的 $A$ 阵列 :

$\displaystyle 3{\lfloor}{\lfloor}n/5{\rfloor}/2+2{\rfloor}$ 个元素大於等於 $x$ ，(在由中位数划分出的子阵列中，有 ${\lfloor}n/5{\rfloor}/2+2$ 个元素大於等於 $x$ )

BFPRT效率分析

由上面的推论，我们可以得到以下性质

$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%203%7B%5Clfloor%7D%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D%2F2%7B%5Crfloor%7D%20%3E%3D%20%5Cfrac%20%7B3n%7D%20%7B10%7D$ 个元素小於等於 $x$
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%203%7B%5Clfloor%7D%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D%2F2%20%2B%202%7B%5Crfloor%7D%20%3E%3D%20%5Cfrac%20%7B3n%7D%20%7B10%7D%20%2B%206$ 个元素大於等於 $x$

由上面这个性质我们可以知道，最多我们可以产生出一个 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%200%3A%5Cfrac%20%7B3n%7D%20%7B10%7D%20%2B%20%5Cfrac%20%7B3n%7D%20%7B10%7D%20%2B%206$ 个元素的分割情况，为了求上界，我们简化成最多产生出 $https://chart.googleapis.com/chart?cht=tx&chl=0%3A%5Cfrac%20%7B7n%7D%20%7B10%7D$ 的分割情况，也就是在第5步中，BFPRT递回呼叫做多作用在 $https://chart.googleapis.com/chart?cht=tx&chl=%5Cfrac%20%7B7n%7D%20%7B10%7D$ 个元素上。

下面推导BFPRT演算法最坏情况的执行时间 $T(n)$

拆分阵列需要 $O(n)$
固定阵列大小的排序，需要的时间是固定的，因此为 $O(n)$
递回呼叫需要 $T({\lfloor}n/5{\rfloor})$
划分需要 $O(n)$
递回呼叫最多需要 $https://chart.googleapis.com/chart?cht=tx&chl=T(%5Cfrac%20%7B7n%7D%20%7B10%7D)$

因此， $T(n)$ 的上限为以下关系式
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20T(n)%3C%3DT(%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D)%2BT(%5Cfrac%20%7B7n%7D%20%7B10%7D)%2BO(n)$ ，使用代换法求解

假设 $T(n)<=cn$ ，则
$https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20T(n)%3C%3DT(%7B%5Clfloor%7Dn%2F5%7B%5Crfloor%7D)%2BT(%5Cfrac%20%7B7n%7D%20%7B10%7D)%2BO(n)$
$\displaystyle \\=1/5*cn+7/10*cn+O(n)$
$\displaystyle \\=9/10*cn+O(n)$
$\displaystyle \\=cn-(1/10*cn-O(n))$ ，如果常数 $c$ 足够大，则 $(1/10*cn-O(n))$ 为非负的项，观察可以发现，只要我们 $c$ 取 $10$ 的任意倍数，就可以实现了，而当 $n <= 50$ ，则 $T(n)$ 为 $O(1)$ ，如果 $c$ 足够大，则 $T(n)$ 的上限就是 $cn$ ，也就是线性时间。