合并和合并排序将在合并排序算法中运行多少次？

Question

这些是家庭作业问题，但我想了解它们背后的概念，而不仅仅是得到答案。

我知道MergeSort的运行时间是O（nlogn）。似乎合并方法必须运行 n 次（因为它必须合并所有数组，最终会有 n 个数组）。因此，我想我可以推断出 MergeSort（） 方法将被称为 logn times。我也认为这是有道理的，因为它正在划分数组，所以它会一直将自己除以 2，所以 logn。

因此，我觉得答案分别是C和A。但我有点怀疑，因为纸条上说问题是问方法被调用了多少次，而不是运行时间。我希望得到一些建议和对计数与运行时间的解释。谢谢你。

问题如下：

18.我们定义了一个递归方法MergeSort（），将输入数组划分在中间，并递归排序每个部分。

假设我们有一个长度为n的数组，我们应用这个合并排序算法。MergeSort（）方法会被调用多少次？

A. O（n）B. O（n2）C. O（log（n））D. O（n log（n））

[[[请注意，这个问题和下一个问题要求计算方法被调用的次数。这与运行时间无关；这是关于计数。]]]

19.假设我们有一个长度为n的数组，我们应用这个合并排序算法。merge（）方法将被调用多少次？

A. O（n）B. O（n2）C. O（log（n））D. O（n log（n））

源代码：

import java.util.Arrays;

public class MergeSort
{
public static void merge(int[] data, int first, int last)
{
    int[] temp = new int[last - first + 1]; // A new array to hold the merged result
    int mid = (first + last) / 2;
    int i = first, j = mid + 1, k = 0;

    // Copy smaller item from each subarray into temp until one
    // of the subarrays is exhausted
    while (i <= mid && j <= last)
    {
        if (data[i] < data[j])
            temp[k++] = data[i++];
        else
            temp[k++] = data[j++];
    }

    // Copy remaining elements from first subarray, if any
    while (i <= mid)
        temp[k++] = data[i++];

    // Copy remaining elements from second subarray, if any
    while (j <= last)
        temp[k++] = data[j++];

    // Copy merged data back into original array
    for (i = first; i <= last; i++)
        data[i] = temp[i - first];
}

public static void merge2(int[] data, int first, int last)
{
    int mid = (first + last) / 2;
    int i = first, j = mid + 1;
    int len = last - first + 1;
    int[] temp = new int[len];

    for (int k = 0; k < len; k++)
    {
        if (i == mid + 1)               // The left part is done
            temp[k] = data[j++];
        else if (j == last + 1)         // The right part is done
            temp[k] = data[i++];
        else if (data[i] < data[j])     // Get one from the left
            temp[k] = data[i++];
        else                            // Get one from the right
            temp[k] = data[j++];
    }

    // Copy merged part back into the original array
    for (i = first; i <= last; i++)
        data[i] = temp[i - first];
}

public static void mergeSort(int[] data, int first, int last)
{
    // intermediate result
    System.out.println(Arrays.toString(Arrays.copyOfRange(data, first, last + 1)));

    if (first >= last)
        return;

    int mid = (first + last) / 2;
    mergeSort(data, first, mid);
    System.out.println("testingMerge");
    mergeSort(data, mid + 1, last);
    System.out.println("testingMerge");

    // merge two sorted parts
    merge(data, first, last);   //merge2(data, first, last);

    // intermediate result

}


public static void main(String[] args)
{
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    System.out.println("begin with: \n" + Arrays.toString(array));
    System.out.println("------------------");

    mergeSort(array, 0, array.length - 1);

    System.out.println("------------------");
    System.out.println("end with: \n" + Arrays.toString(array));
    }
}

Answer 1

你的答案似乎是正确的。

我们定义了一个递归方法MergeSort()，将输入数组一分为二，递归排序每一部分。

所以我们期望调用< code > merge sort < code > log n 次。因为每个递归步骤是< code>n长度的一半。

因为我们知道合并排序是O(n log n)可以在这里停止，因为< code>MergeSort被调用< code>log n次，所以< code>merge必须被调用< code>n次。但是我们也可以推理，我们必须细分< code>n个项目，直到每个输入包含一个元素。显然，我们必须合并< code>n个这样的项目列表，以得到由< code>n个项目组成的最终结果。