试证明，在最坏情况下，求n个元素组成的集合s中的第k小元素至少需要n+min(k,n- k+1)-2次比较_试证明,在最坏情况下,求n个元素组成的集合s中的第k小元素至少需要n+min(k,n-k+1)-

问题描述

试证明，在最坏情况下，求n个元素组成的集合s中的第k小元素至少需要n+min(k,n- k+1)-2次比较。

问题分析

问题分析：

• 我们在之前已经学习了分治选择算法RandomizeSelect算法，该算法可以在一个线性时间里求解序列中的第K个元素，但是很遗憾，我们没法从该算法入手解决这个证明问题。因为此证明，试图证明所有选择算法的——极限所在，准确来说是下限
• 你是否记的，在数据结构中我们曾证明排序算法的极限是nlogn，想必你还没忘记是如何证明的，没错，但是我们使用树状的图形——比较树
• 本题的证明策略试图利用类似于比较树的图形来解决这个问题，经过实践，还需要一些更高明的办法
  证明思路如下：

（1）用序关系树描述整个比较过程
（2）用对手策略来构造一种比较策略，使得算法尽量多的多做比较，从而求解时间下限

序关系树

对手策略

• 若用P表示所讨论的问题，I表示问题的输入，A表示解决问题的基于比较运算的算法，T（A，I）表示对于输入I，
  算法A的计算时间复杂性，那么函数
  U（n）=min{max{T(A，I)}，for each I}，for each A
  表示问题P在输入大小为n时在最坏情况下的最好时间下界，它是问题所固有的。问题P的这个最好时间下界通常很难通
  过定义得到，因为计算max{T(A，I)}，for each I是一件很难的事，更何况对于一切的A，因此，人们往往不精确地求U（n）
  而是退而求其次，即寻找一个f（n），它不大于U（n），但尽量接近于U（n），使f（n）成为P的一个好的下界。
• 对手论证方法是找到f（n）的一个有效方法，它的基本思想是对每一个A构造一个输入特殊的输入I’，使T（A，I’）尽量地大
  然后在所有A的集合上，求T（A，I’）的尽量小的下界作为f（n）,这种方法通过F（n）<= min{T(A，I’)}，for each A<= min{max{T(A，I)}，for each I}，for each A = U（n）

对手策略的关键：

• 有一套对于一切算法的适用的构造符合要求的I’的策略，即对手策略
  逐步第构造出一个输入I’使算法A如果想达到预期的结果，要做尽量多次的比较和判断，从而使T（A，I’）尽量大。
• 一方面对手策略需具有一致性，即不能前后矛盾，以保证I’的存在性；
• 另一方面对手策略还必须对一切A都适用，因为我们需要在一切A组成的集合上求T（A，I’）得下界。至于策略的具体内容将因题而异，甚至同一个问题肯能有多种策略，要得到好的下界需要好的策略。

证明

（1）构造对手策略

基于比较的算法中，可以通过三种方式确定某一元素与z的关系：
1、该元素与z比较，便可确定其与z的大小关系；
2、该元素比一个确定比z大的元素大，则该元素比z大；
3、该元素比一个确定比z小的元素小，则该元素比z小，这三种比较称为关键比较，由于集合中有n个元素，所以至少需要n-1次关键比较，才能确定集合中的第k小元素。（这和之前的有序关系树一致）
基于比较的算法过程中还剩余两种无用比较，即某一元素：
1、该元素比大于z的元素小；
2、该元素比小于z的元素大；
这两种情况我们无法确定该元素与z的关系，得不到有用信息，为非关键比较，为降低算法时间复杂度，减少比较次数，我们希望尽可能的多做关键比较，少做无用比较，而所谓对手策略，便是迫使我们尽量多做非关键比较，以获取尽量大的T（A，I’），即最坏情况。在算法执行的任何阶段，集合中的元素有以下三种状态：
1、L——该元素的值已确定大于z
2、S——该元素的值已确定小于z
3、N——该元素的值不确定
每当算法做两个元素x和y的比较时，对手策略根据x和y的状态，按照下表确定状态为N的元素的值

（2）证明

• 对手策略中的每个比较均为非关键比较每个这类比较最多产生一个元素状态L或S，算法最终产生k-1个状态为S的元素和n-k个状态为L的元素
• 因此，上述对手策略至少迫使产生做了min(k-1，n-k)次非关键比较。
• 因此任何算法在求第k小元素上至少做了n-1+min(k-1，n-k)次比较
  由此可见，在最坏情况下，第k小元素问题至少需要n-1+min(k-1，n-k)-次比较，

即 n+min(k，n-k+1)-2 次比较