2

バロメーター操作と呼ばれる方法を使用して、マージソートの命令数を見つける必要があります。

気圧計の操作とは何ですか？

  • 「気圧計命令」が選択されている
  • カウント=気圧計命令が実行された回数。
  • 検索アルゴリズム：気圧計命令（x == L [j]？）。
  • ソートアルゴリズム：気圧計命令（L [i] <= L [j]？）。

例：-

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

バロメーター操作=+ループ本体内

count（+）= n

したがって、マージソートの問題は、それが再帰的アルゴリズムであり、特定の命令が実行された回数を数えることができるように、特定の命令を選択する方法がわからないことです。

4

2 に答える 2

0

ウィキペディアのコードを使用してみましょう。あなたは分割された部分を頼りにする必要があります。分割は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)。

于 2013-03-10T22:00:38.257 に答える
0

正しい方向を示してくれた@aphexと@SGM1に感謝します。問題の解決策は次のとおりだと思います。

使用したaphexと同じコードを使用しました。しかし、解決策の唯一の問題は、aphexが最悪の場合にそれを維持することを忘れていることです。だから私によると、気圧計の操作/指示は

first(left) <= first(right)

これが実際の比較が行われている場所だからです。気圧計の演算子は、実際の比較が行われる場所では「<=」になります。そして、この演算子は、リストを分割する2つの方法によって再帰的に（n / 2）回呼び出され、メインのマージ操作は正確に（n-1）回発生します。したがって、和分方程式を解いた後、（nlog（n）+ c）が得られます。

aphexによる変更がほとんどないWikiのコード 

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
于 2013-03-11T16:41:40.863 に答える