选择问题的比较复杂度研究

• 作 者: 曾钢
• 机 构: 中国科学院大学
• 出 处: 中国科学院大学
• 发表日期: 2017年期
• 关键词: 计算复杂性理论 选择问题 比较复杂度

选择问题定义如下:给定由n个元素组成的集合A和一个正整数1≤k≤n，A中两两元素之间存在大于或小于关系，选择问题要求在A中找到第k小的元素，即找到一个元素，恰好大于k-1个元素并且恰好小于n-k个元素。选择问题是计算复杂性领域的经典问题之一，被应用于排序、找凸包等问题中。一般考虑它在比较模型下的复杂度。比较模型限定对数据的访问只可以两两比较，并且算法的复杂度以算法执行过程中的比较次数衡量。称算法的比较复杂度为算法在比较模型中的复杂度。　　1973年，Blum等人对选择问题提出了一个确定性算法，算法需要将给定的集合A分成若干大小为g的小块。Blum等人证明，如果g≥5，则算法的比较复杂度为O(n)。而如果g∈{3，4}，虽然按照Blum等人的分析，算法的比较复杂度为O(nlogn)，但是没有例子证明这个分析是紧的。　　本文首先证明，如果g=2，则Blum等人算法的比较复杂度为Ω(nlogn)。然后对Blum等人算法的分块策略做了调整，使得当g∈{3，4}时算法的比较复杂度为Θ(nlogn)。本文也对Blum等人的算法稍作修改，当g∈{3，4}时，对于任意的分块策略，有比较复杂度为O(n)。定义A中的（m，k）平凡元素为A中小于m个元素并且大于k个元素的元素，其中A的规模为n且n≥m+k+1。本文证明了当n大于一定阈值时，找到（m，k）平凡元素需要的比较次数不超过（1+√2α）2（m+k+1），其中α=k/m+k+1。