区块链毕设网qklbishe.com为您提供问题的解答

（小顺序统计量）要在n个数中选出第i个顺序统计量，SELECT在最坏情况下需要的比较次数T(n)满足T(n)=。但是，隐含在记号中的常数项是非常大的，当i相对n来说很小时，我们可以实现一个不同的算法，它以SELECT作为子程序，但在最坏情况下所做的比较次数更少。

                                      

（提示：从个不相交对的两两比较开始，然后对由每对中的较小的元素构成的集合进行递归。）

d.证明：如果对所有有i=n/k，则U_i(n)=n+O(T(2n/k)lgk)。

以上就是关于问题（小顺序统计量）要在n个数中选出第i个顺序统计量，SELECT在最坏情况下需要的比较次数T(n)满足T(n)=。但是，隐含在记号中的常数项是非常大的，当i相对n来说很小时，我们可以实现一个不同的算法，它以SELECT作为子程序，但在最坏情况下所做的比较次数更少。 a.设计一个能用Ui(n)次比较在n个元素中找出第i小元素的算法，其中，                                        （提示：从个不相交对的两两比较开始，然后对由每对中的较小的元素构成的集合进行递归。） b.证明：如果i<n/2，则有Ui(n)=n+O(T(2i)lg(n/i))。 c.证明：如果i是小于n/2的常数，则有Ui(n)=n+O(lgn)。 d.证明：如果对所有有i=n/k，则Ui(n)=n+O(T(2n/k)lgk)。
SELECT算法的思想是要保证对数组的划分是个好的划分，对PARTITION过程进行了修改。现在通过SELECT算法来确定n个元素的输入数组中的第i小的元素，具体操作步骤如下：
（1）将输入数组的n个元素划分为n/5（上取整）组，每组5个元素，且至多只有一个组有剩下的n%5个元素组成。
（2）寻找每个组织中中位数。首先对每组中的元素（至多为5个）进行插入排序，然后从排序后的序列中选择出中位数。
（3）对第2步中找出的n/5（上取整）个中位数，递归调用SELECT以找出其中位数x。（如果是偶数去下中位数）
（4）调用PARTITION过程，按照中位数x对输入数组进行划分。确定中位数x的位置k。
（5）如果i=k，则返回x。否则，如果i<k，则在地区间递归调用SELECT以找出第i小的元素，若干i>k，则在高区找第(i-k)个最小元素。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训