如何求最小值
ppip
·
2025-05-26 16:28:28
·
休闲·娱乐
以下介绍一个全新的只用比较求出 n 个元素最小值的算法：
随机选 k 个元素，然后递归地找到这 k 个元素的最小值。此时该最小值的排名期望不超过 \frac{n}{k}。用这个元素和剩余的 n-k 个元素比较，把其中比这个元素小的元素取出来，递归找这一部分的最小值。
找最小值的比较次数期望不超过 C(n)=C(\frac{n}{k})+C(k)+n-k，时间复杂度为 T(n)=T(\frac{n}{k})+T(k)+O(n)。
选取不同的 k 可以平衡使用的比较次数与时间复杂度。例如：
该算法十分灵活，扩展性强，不失为一种好的求最小值的方法。