遞歸算法情況下的氣壓計操作

Question

我必須使用稱爲氣壓計操作的方法找到合併排序的指令計數。

什麼是氣壓計操作？

• A「晴雨表指令」被選擇
• 計數=的被執行的指令晴雨表次數。搜索算法：氣壓計指令（x == L [j]？）。
• 排序算法：氣壓計指令（L [i] < = L [j]？）。

對於例如： -

 for(int i=0;i < n;i++) 
     A[i] = i + 1 

晴雨表操作循環的體= +

計數（+）= N

所以，現在問題歸併排序就是它是遞歸算法，我不知道如何選擇一個特定的指令，以便我可以計算特定指令的次數被執行。

Answer 1

感謝@aphex和@ SGM1向我展示了正確的方向。我想問題的解決方案如下：

我使用相同的代碼aphex使用。但只有解決方案的問題是，aphex忘記維護它的最壞情況。所以，根據我的晴雨表操作/指令必須是

first(left) <= first(right)

，因爲這是實際的比較是怎麼回事。氣壓計操作員將在「< =」進行實際比較。這個運算符被兩個方法遞歸地（n/2）次遞歸地分割列表，然後主合併操作恰好發生（n-1）次。因此，在求解求和方程後給出（nlog（n）+ c）

代碼從維基幾乎不做修改通過APHEX

function merge_sort(list m, var count) 
    if(length(m))>0 
     count++; 

// if list size is 0 (empty) or 1, consider it sorted and return it 
// (using less than or equal prevents infinite recursion for a zero length m) 
if length(m) <= 1 
    return m 

// else list size is > 1, so split the list into two sublists 
var list left, right 
var integer middle = length(m)/2 
for each x in m before middle 
    add x to left 
for each x in m after or equal middle 
    add x to right 
// recursively call merge_sort() to further split each sublist 
// until sublist size is 1 
left = merge_sort(left,count) 
right = merge_sort(right,count) 
// merge the sublists returned from prior calls to merge_sort() 
// and return the resulting merged sublist 
return merge(left, right) 

function merge(left, right) 
var list result 
while length(left) > 0 or length(right) > 0 
    if length(left) > 0 and length(right) > 0 
     if first(left) <= first(right) // My Barometer Operation 
      append first(left) to result 
      left = rest(left) 
     else 
      append first(right) to result 
      right = rest(right) 
    else if length(left) > 0 
     append first(left) to result 
     left = rest(left) 
    else if length(right) > 0 
     append first(right) to result 
     right = rest(right) 
end while 
return result 

Answer 2

讓我們使用Wikipedia的代碼。你需要指望分裂的部分。拆分在merge_sort(list m)中進行。您需要添加計數器作爲輸入參數（var count），請參閱下文。該計數器必須是count=0。每次方法被調用和列表lenght>0，那麼您可以通過1

function merge_sort(list m, var count) 
     // Count here 
    if(length(m))>0 
      count++; 

    // if list size is 0 (empty) or 1, consider it sorted and return it 
    // (using less than or equal prevents infinite recursion for a zero length m) 
    if length(m) <= 1 
     return m 

    // else list size is > 1, so split the list into two sublists 
    var list left, right 
    var integer middle = length(m)/2 
    for each x in m before middle 
     add x to left 
    for each x in m after or equal middle 
     add x to right 
    // recursively call merge_sort() to further split each sublist 
    // until sublist size is 1 
    left = merge_sort(left,count) 
    right = merge_sort(right,count) 
    // merge the sublists returned from prior calls to merge_sort() 
    // and return the resulting merged sublist 
    return merge(left, right) 

function merge(left, right) 
    var list result 
    while length(left) > 0 or length(right) > 0 
     if length(left) > 0 and length(right) > 0 
      if first(left) <= first(right) 
       append first(left) to result 
       left = rest(left) 
      else 
       append first(right) to result 
       right = rest(right) 
     else if length(left) > 0 
      append first(left) to result 
      left = rest(left) 
     else if length(right) > 0 
      append first(right) to result 
      right = rest(right) 
    end while 
    return result 

增加計數器對於需要調用這樣merge_sort([38,27,43,3,9,82,10], 0)僞代碼維基百科的例子。