线性选择算法在Java中是如何实现和描述的？

本文共计772个文字，预计阅读时间需要4分钟。

使用五位数中值选取算法的快速选择算法运行时间为O(n)。假设（a1+a2+...+ak）1/（k0），则总时间为T(N)T(a1N)+T(a2N)+...+T(akN)+O(使用五位数中值选取算法的快速选择算法的运行时间)。

使用五位数中值取中分割法的快速选择算法的运行时间为O（n）定理：如果（a1+a2+···+ak)1(k0),则方程T(N)T(a1N)+T(a2N)+···+T(akN)+O(

使用五位数中值取中分割法的快速选择算法的运行时间为O（n）

定理：如果（a₁+a₂+···+a_k)0),则方程T(N)=T(a₁N)+T(a₂N)+···+T(a_kN)+O(N)的解为T(N)=O(N)

分析：如果有10k+5个数组成的数组，在这种情况下，对这个数组进行五位数一组的分割，一共得到2k+1组数，则存在k个小于中值的中值的数（命名为S）和k个大于中值的中值的数（命名为L），至少有（k+2k+2）S和（k+2k+2）个L。于是在这种情况下，递归调用最多可以包含(10k+5)-(3k+2)-1=7k+2个数，7k+2<0.7*(10k+5)。而对分组的中值取中采用递归，时间复杂度为T(N/5)。对N/5个组进行5个数的冒泡排序，时间复杂度为O(N)。