2

我必须使用称为气压计操作的方法找到合并排序的指令计数。

什么是气压计操作？

  • 选择了“气压计指令”
  • 计数 = 气压计指令执行的次数。
  • 搜索算法：气压计指令（x == L[j]？）。
  • 排序算法：气压计指令（L[i] <= L[j]?）。

例如：-

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

气压计操作 = +在循环体中

计数（+）= n

所以现在合并排序的问题是它是递归算法，我不知道如何选择一个特定的指令，以便我可以计算特定指令执行的次数。

4

2 回答 2

0

感谢@aphex和@SGM1向我展示了正确的方向。我想问题的解决方案如下：

我使用了与aphex相同的代码。但解决方案的唯一问题是aphex忘记在最坏的情况下维护它。所以根据我的气压计操作/说明必须是

first(left) <= first(right)

因为这是进行实际比较的地方。晴雨表运算符将是“<=”进行实际比较的地方。并且该运算符通过两种划分列表的方法递归调用 (n/2) 次，然后主合并操作恰好发生 (n-1) 次。因此在求解求和方程后，它给出 (nlog(n)+c)

来自 Wiki 的代码，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
于 2013-03-11T16:41:40.863 回答
0

让我们使用来自Wikipedia的代码。您需要依靠拆分部分。拆分是在merge_sort(list m).. 中进行的。您需要将计数器添加为输入参数（var count），见下文。计数器必须是count=0。每次调用方法和 listlenght>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

对于 wikipedia 示例，您需要像这样调用伪代码merge_sort([38,27,43,3,9,82,10], 0)。

于 2013-03-10T22:00:38.257 回答