为什么递归合并排序函数显示O(n ^ 2)时间复杂度 [英] Why is recursive merge sort function displaying O(n^2) time complexity
问题描述
我尝试递归地实现合并排序，但是不幸的是，它似乎显示O(n ^ 2)复杂度，而不是所需的O(nlogn). 这是代码，首先我调用一个驱动程序方法(在这里创建temp数组，因此不需要为每个递归调用都重新初始化):
I have tried implementing a merge sort recursively, and unfortunately, it seems to be displaying O(n^2) complexity rather than the desired O(nlogn). Here is the code, first I call a driver method(creating the temp array here so it doesn't need to reinitialize for every recursive call):
public static <T> void mergesort(ArrayList<T> list, Comparator<? super T> comparator) {
// Create and initialize a temporary ArrayList to be passed through the
// recursive method.
ArrayList<T> temp = new ArrayList<T>();
for (int i = 0; i < list.size(); i++) {
temp.add(null);
}
mergeSortRecursive(list,temp, 0, list.size()-1, comparator);
}
一旦处理了所有驱动程序业务，就会调用mergeSortRecusive(一旦子数组达到一定大小，我便切换到插入排序.在这种情况下，INSERTTHRESHOLD设置为10):
Once all the driver business is handled mergeSortRecusive is called(I switch to insertion sort once the subarrays reach a certain size. In this case INSERTTHRESHOLD is set to 10):
private static <T> void mergeSortRecursive (ArrayList<T> list, ArrayList<T> temp, int left, int right, Comparator<? super T> comparator) {
// If ArrayList size is less than the set threshold call the insertSort
// method and return results instead continuing to call the recursive method.
if(right - left < INSERTTHRESHOLD) {
insertionSort(list, left, right, comparator);
}
// Find mid point in ArrayList biased on size of array.
int mid = (left + right) / 2;
// Recursively call the mergeSortRecursive method passing the first half of the
// ArrayList.
mergeSortRecursive(list,temp, left, mid, comparator);
// Recursively call the mergeSortRecursive method passing the second half of the
// ArrayList.
mergeSortRecursive(list,temp, mid+1, right, comparator);
// Merge the two half array lists back together and return the results.
merge(list,temp, left, mid+1, right, comparator);
}
最后，一旦一切顺利并分解，就会调用merge函数将其重新组合在一起:
Lastly, once everything is nice and split up the merge function is called to bring it all back together:
private static <T> void merge (ArrayList<T> list, ArrayList<T> temp, int start, int mid, int end, Comparator<? super T> comparator) {
int i1 = start, i2 = mid;
int index = start;
// Loop through each Array list together.
while (i1 < mid && i2 < end+1) {
// If the item in the first ArrayList is smaller than the second
// add that item to the temporary list and increment the index
// of the first iterator.
if(comparator.compare(list.get(i1), list.get(i2)) < 0) {
temp.set(index, list.get(i1));
index++;
i1++;
}
// If the item in the first ArrayList is not smaller than the second
// add the second ArrayList item to the temporary list and increment the index
// of the second iterator.
else {
temp.set(index, list.get(i2));
index++;
i2++;
}
}
// Add all remaining items from second ArrayList.
while(i2 < end+1) {
temp.set(index, list.get(i2));
index++;
i2++;
}
// Add all remaining items from first ArrayList.
while(i1 < mid) {
temp.set(index, list.get(i1));
index++;
i1++;
}
//Replace the order of the list with the temporary list.
for (int i = start; i <end+1 ; i++) {
list.set(i,temp.get(i));
}
}
以下是时间图:
这是n ^ 2上的平均时间:
Here's the average time over n^2:
这是经过n * log(n)的时间:
here's the time over n*log(n):
那为什么要花这么长时间?
So why is taking this thing so long?
推荐答案
可以在系统上测试此示例代码吗?这是一种优化的自上而下的合并排序，可对int(原始)进行操作.本示例将在约1.2秒内对10,000,000个整数进行排序.对于您的示例，我想知道所有这些set调用的开销(这些释放和分配内存吗?)，以及arraylist(指向对象的指针数组)的开销.
Could you test this example code on your system? It's an optimized top down merge sort that operates on int (primitive). This example is sorting 10,000,000 ints, in about 1.2 seconds. For your example, I'm wondering about overhead of all those set calls (do these release and allocate memory?), and the overhead of an arraylist (array of pointers to objects).
package jsorttd;
import java.util.Random;
public class jsorttd {
static void MergeSort(int[] a) // entry function
{
if(a.length < 2) // if size < 2 return
return;
int[] b = new int[a.length];
MergeSortAtoA(a, b, 0, a.length);
}
static void MergeSortAtoA(int[] a, int[] b, int ll, int ee)
{
if(ee - ll > 1) {
int rr = (ll + ee)>>1; // midpoint, start of right half
MergeSortAtoB(a, b, ll, rr);
MergeSortAtoB(a, b, rr, ee);
Merge(b, a, ll, rr, ee); // merge b to a
}
}
static void MergeSortAtoB(int[] a, int[] b, int ll, int ee)
{
if(ee - ll > 1) {
int rr = (ll + ee)>>1; // midpoint, start of right half
MergeSortAtoA(a, b, ll, rr);
MergeSortAtoA(a, b, rr, ee);
Merge(a, b, ll, rr, ee); // merge a to b
} else if((ee - ll) == 1) { // if just one element
b[ll] = a[ll]; // copy a to b
}
}
static void Merge(int[] a, int[] b, int ll, int rr, int ee) {
int o = ll; // b[] index
int l = ll; // a[] left index
int r = rr; // a[] right index
while(true){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
do // else copy rest of right run
b[o++] = a[r++];
while(r < ee);
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
do // else copy rest of left run
b[o++] = a[l++];
while(l < rr);
break; // and return
}
}
}
public static void main(String[] args) {
int[] a = new int[10000000];
Random r = new Random();
for(int i = 0; i < a.length; i++)
a[i] = r.nextInt();
long bgn, end;
bgn = System.currentTimeMillis();
MergeSort(a);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i++){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " + (end-bgn));
}
}
这篇关于为什么递归合并排序函数显示O(n ^ 2)时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
