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

考虑每组分为k个元素。则大于或小于中位数的中位数的数至少为

因此在最坏情况下SELECT将处理最多n-(n/4-k)=3n/4+k个元素。

递归式

用代换法解决，假设算法是线性的，猜测有T(n)<=cn。

其中最后只在k>=4时成立。

因此该算法对4个及4个以上的分组是线性的。当k=3时该算法的复杂度是Ω(nlgn)。

以上就是关于问题在SELECT算法中，输入元素被分为每组5个元素。如果它们被分成每组7个元素，该算法仍然会是线性的吗？证明：如果分成每组3个元素，SELECT的运行时间不是线性的。
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链游项目方科学家脚本开发培训