[發明專利]一種語義驅動的中位數選擇算法

在審

• 申請號: 201711329427.6
• 申請日: 2017-12-13
• 公開（公告）號: CN108009133A
• 公開（公告）日: 2018-05-08
• 發明（設計）人: 段玉聰;邵禮旭;宋正陽
• 申請（專利權）人: 海南大學
• 主分類號: G06F17/18
• 分類號: G06F17/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明是一種語義驅動的中位數選擇算法，具體涉及一種尋找偶數個數值的中位數算法，屬于數據結構與算法領域。本發明分析了兩種迭代的模式分別是2*3模式（2個三元組）和2*6（2個六元組）模式，可以保證中位數候選數量的顯著減少?；趯@2種模式的分析，本發明設計了一種算法來尋找偶數個數值的中位數。

技術領域

本發明提供一種語義驅動的中位數選擇算法，具體涉及一種尋找偶數個數值的中位數算法，屬于數據結構與算法領域。

背景技術

一個數據集合的中位數通常是很一個很有價值的統計指標，由于它對異常數據不敏感，所以一般會比平均值更能體現數據集合數據的“平均水平”。然而，對于無序數據序列求中位數在實現上卻沒有求平均值那樣簡單優美的O (N)復雜度的算法。最容易想到的做法是先對數據進行排序，然后取中點的值，然而這種做法的時間復雜度是O(NlogN)。

發明內容

本發明目的是提供一種語義驅動的中位數選擇算法，來尋找偶數個數的中位數。中位數選擇問題定義如下：給定一個有N個不同數字的數組ARR，找到一個中位數x或一對中位數（x，y）。因此，若N是奇數，則存在一個數arrx既大于（N-1）/ 2個數，也小于（N-1）/ 2個數；而若N是一個偶數，則有一對數arrx和arry，既大于（N-2）/ 2個其他的數，也小于（N-2）/2個其他的數。本發明為找到一張最有效的且是可計算的解決方案來定位中位數，實現一個語義導向的設計，制訂了以下規則：

（a）排他性：當試圖構造一個問題的算法時，只有基本的問題描述才能被理想地假設為完整的問題描述；

（b）完整性：在完成算法的設計時，從基本的問題描述中充分地探索必要的語義；

（c）兼容組合一致性：遵循上述排他性和完整性的規則，所得到的算法可以被視為對基本問題描述語義的形式化轉換。作為一個整體，本發明提出對問題描述部分的組成語義進行操縱以符合整個問題描述的一般語義

本發明提出分析整個過程中的排除階段，遞歸縮小搜索范圍。設N>=6且N能被3整除，將N分成N/3個部分，每個部分里的三個數字按升序排列，表示為(sx,mx,lx)，sx表示較小的數字，mx表示中位數，lx表示較大的數字，通過兩種模式遞歸縮減搜索范圍，本發明設NM表示在一個給定的數組中中位數可能存在的位置，PN表示對應位置上的數字在排序處理后可能對應的序號范圍，ML表示左側中位數，MR表示右側中位數，把每個階段累計排除的數字的影響當作關鍵的考慮因素，ex表示數字被排除，提出以下分析：

（1）2*3模式—兩組三元組模式

設有兩對三元組a和b，

三元組a:(sa,ma,la)->PN(1-4,2-5,3-6),

三元組b:(sb,mb,lb)->PN(1-4,2-5,3-6),

NM(6)={3,4}.

對于兩個三元組，最多需要3次比較來得到三元組的中位數：

如果mb>ma，則(sa,ma,la-ex)->PN(1-4,3-5,5-6),(sb-ex,mb,lb)->PN(1-2,2-3,3-6);

如果sa<mb，則(sa-ex, ma, la-ex)->PN(1-2,4-5,5-6),(sb-ex, mb-ML, lb)->PN(1-2,3-3,4-6);