3

A partner and I are attempting to program Mergesort in Java. We have completed the algorithm, and it functions properly. However, in testing the algorithm for a variety of inputs, we noticed that it does not perform within the bound of O(Nlog(N)). We have been attempting to optimize the algorithm further and would appreciate any and all suggestions. The only requirement is that we cannot change the method headers. Our Java code is listed below:

    /**
 * 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();

}
4

2 回答 2

6

将我的评论转换为答案 -

说一个算法的运行时间为 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 的值是无量纲的（它测量一个数量），而运行时间以秒为单位，所以这里正在进行一些单位转换。

希望这可以帮助！

于 2013-06-14T01:41:03.513 回答
0

由于@templatetypedef 已经转换了 BigO 部分，让我们转到优化部分。我不懂Java语言，但方法是不言自明的。我注意到您在合并时不断添加和清除临时列表。

temp.add(arr.get(currentLeft++));
// ...
// ...
temp.add(arr.get(rightStart++));
// ...
// ...
temp.clear();

将项目附加到数组中不需要固定时间。

于 2013-06-14T01:47:23.697 回答