java - 在 Java 中针对 O(Nlog(N)) 优化归并排序

Question

我和一个合作伙伴正在尝试用 Java 编写归并排序程序。我们已经完成了算法，并且可以正常运行。然而，在针对各种输入测试算法时，我们注意到它不在 O(Nlog(N)) 的范围内执行。我们一直在尝试进一步优化算法，并会感谢任何和所有建议。唯一的要求是我们不能更改方法 header 。下面列出了我们的 Java 代码:

    /**
 * MergeSort algorithm driver.
 * 
 * @param arr - input ArrayList of objects
 */
public static <T extends Comparable<? super T>> void mergesort(
        ArrayList<T> arr)
{
    // Pre-allocation of a temporary ArrayList
    // for merge space.
    ArrayList<T> temp = new ArrayList<T>(arr.size());
    temp.addAll(arr);

    // Call the recursive mergesort method.
    mergesort(arr, temp, 0, arr.size() - 1);
}

/**
 * Main mergeSort method. Makes recursive calls. 
 * 
 * @param arr - input ArrayList of objects
 * @param temp - temporary ArrayList to hold the merged result 
 * @param left - start of the subarray 
 * @param right - end of the subarray
 */
private static <T extends Comparable<? super T>> void mergesort(
        ArrayList<T> arr, ArrayList<T> temp, int left, int right)
{

    // If the size of the subcollection is less than a given threshold,
    // then perform an insertion sort rather than a mergesort.
    //if ((right - left) < threshold)
    //  insertionsort(arr, left, right);


    // If the size of the subcollection was not less than our threshold and 
    // the left end is less than the right end of subcollection, then we are 
    // done performing the sort.
    if(left < right)
    {
        int center = (left + right) / 2;
        mergesort(arr, temp, left, center);
        mergesort(arr, temp, center + 1, right);
        merge(arr, temp, left, right);
    }
}

/**
 * Internal method for merging two sorted subarrays. This is to be used with the 
 * mergesort algorithm.
 * 
 * @param arr - input ArrayList of objects
 * @param temp - temporary ArrayList in  which the result with be placed
 * @param currentLeft - start of the subarray 
 * @param rightEnd - end of the subarray
 */
private static <T extends Comparable<? super T>> void merge(
        ArrayList<T> arr, ArrayList<T> temp, int leftStart, int rightEnd)
{
    int currentLeft = leftStart;
    int leftEnd = (currentLeft + rightEnd) / 2;
    int rightStart = leftEnd + 1;


    // Main loop - compares the value in the left position
    // to the value in the right position.  
    while( currentLeft <= leftEnd &&  rightStart <= rightEnd)
    {
        // If the value in the left position is less than the right, 
        // place the left position value in the temporary collections.
        if(arr.get(currentLeft).compareTo(arr.get(rightStart)) <= 0)
        {
            temp.add(arr.get(currentLeft++));

        }


        // Otherwise, place the value in the rightStart position in
        // the temporary collection.
        else
        {
            temp.add(arr.get(rightStart++));

        }
    }

    // Copy the remaining left half.
    while( currentLeft <= leftEnd )
        temp.add(arr.get(currentLeft++));


    // Copy the remaining right half.
    while( rightStart <= rightEnd )
        temp.add(arr.get(rightStart++));


    // Loop through the temporary collection and for each element
    // currently in the collection, copy the contents back into the
    // original collection.
    for (int i = leftStart, count = 0; i <= rightEnd; i++, count++)
        arr.set(i, temp.get(count));

    // After the above operation has been completed for this particular
    // call, clear the temporary collection.
    temp.clear();

}

Answer 1

将我的评论转换为答案 -

说一个算法的运行时间为 O(n log n) 并不意味着该函数的运行时间将与函数 f(n) = n log n 的绘图完全匹配。相反，它意味着函数的运行时间以与函数 n log n 的运行时间相同的速度增长。因此，对于大 n，如果将输入的大小加倍，运行时间应该略微增加一倍。

您提到函数的运行时间大约是 n log n 值的三倍这一事实实际上有力地证明了您的运行时间为 O(n log n) - 您的函数的运行时间大约为 3n log n，这意味着它的运行时间是 O(n log n)，因为 big-O 忽略了常数因子。为了在数学上更准确 - 您拥有的常数可能不完全是 3，因为 n 的值是无量纲的(它测量数量)，而运行时间以秒为单位，因此这里进行了一些单位转换。

希望这对您有所帮助!