3

パートナーと私は、Mergesort を Java でプログラミングしようとしています。アルゴリズムが完成し、正常に機能しています。ただし、さまざまな入力に対してアルゴリズムをテストしたところ、O(Nlog(N)) の範囲内で実行されないことがわかりました。私たちはアルゴリズムをさらに最適化しようとしており、あらゆる提案を歓迎します. 唯一の要件は、メソッド ヘッダーを変更できないことです。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();

}
4

2 に答える 2

6

コメントを回答に変換する -

アルゴリズムの実行時間が O(n log n)であるということは、関数の実行時間が関数 f(n) = n log n のプロットと正確に一致するという意味ではありません。代わりに、関数の実行時間は、関数 n log n の実行時間と同じ割合で成長することを意味します。したがって、n が大きい場合、入力のサイズを 2 倍にすると、実行時間は 2 倍をわずかに超えるはずです。

関数のランタイムが n log n の値の約 3 倍であると述べたという事実は、実際には O(n log n) ランタイムがあることの強力な証拠です。関数のランタイムは約 3n log n です。つまり、そのランタイムはO(n log n)、big-O は定数係数を無視するため。より数学的に正確に言うと、n の値は無次元 (量を測定する) であり、実行時間は秒単位であるため、定数はおそらく正確に 3 ではないため、ここでいくつかの単位変換が行われます。

お役に立てれば！

于 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 に答える