在归并排序算法中，归并和归并排序将运行多少次?

Question

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

我知道归并排序的运行时间是O(nlogn)。似乎合并方法必须运行n次(因为它必须合并所有数组，最终有n个数组)。因此，我认为我可以推断出MergeSort()方法将被调用logn次。我也认为这是有道理的因为它在除以数组，所以它会一直除以2，也就是logn。

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

问题如下:

18岁。我们定义了一个递归方法MergeSort()，将输入数组划分在中间，并对每个部分进行递归排序。

假设我们有一个长度为n的数组，我们应用这个归并排序算法。将调用MergeSort()方法多少次?

。O (n)b . O (n2)C. O(log(n))D. O(n log(n))

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

19。假设我们有一个长度为n的数组，我们应用这个归并排序算法。merge()方法将被调用多少次?

。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()，将输入数组划分在中间，并对每个部分进行递归排序。

所以我们期望MergeSort乘以log n。因为每个递归步骤是n长度的一半。

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