为什么使用Quicksort获得线性运行时间？

更新：我明白我的问题是什么。每次我排序10000个数据点。每次迭代都需要相同的时间。 t是我尝试对100个数据点进行排序的不正确方法，然后添加接下来的100个数据点，排序等。为什么使用Quicksort获得线性运行时间？

我想表明Quicksort的平均/最佳情况下运行时间是O（nlogn）。但是，当我尝试在大量循环中计算该方法时，我会得到线性运行时间。

我认为它与我实现for循环的方式有关，但我不知道为什么它会出错。

我还有另一个函数，它读取已经排序的数组，给我最坏的情况下运行时间，但是这也给了我线性。

对于这两种功能，时代是这样的：

System.out.println("Enter the number of data points you want to sort as an integer: "); 
Scanner num = new Scanner(System.in); 
int datapoints = num.nextInt(); 
int[] dpArr = new int[datapoints]; 

for (int i = 0; i < datapoints; i++) 
{ 
    dpArr[i] = (int) (Math.random() * 100000); 
} 
int n = dpArr.length; 

try 
{ 
    PrintWriter pw = new PrintWriter(new FileWriter("random2.csv", true)); 
    StringBuilder sb = new StringBuilder(); 
    StringBuilder sb2 = new StringBuilder(); 

    for (int t = 100; t <= 100000; t += 100) 
    { 
     long qstotal = 0; 

     long start = System.nanoTime(); 
     quicksort(dpArr, 0, n - 1); 
     qstotal += System.nanoTime() - start; 

     double qsDuration = (double) qstotal/1000000; 
     sb.setLength(0); 
     sb.append(t); 
     sb.append(','); 
     sb.append(qsDuration);   
     sb.append("\n"); 
     pw.write(sb.toString()); 
    } 

    for (int t = 100; t <= 100000; t += 100) 
    { 
     long rqstotal = 0; 

     long start = System.nanoTime(); 
     randomQuicksort(dpArr, 0, n - 1); 
     rqstotal += System.nanoTime() - start; 

     double rqsDuration = (double) rqstotal/1000000; 
     sb2.setLength(0); 
     sb2.append(t); 
     sb2.append(','); 
     sb2.append(rqsDuration); 
     sb2.append("\n"); 
     pw.write(sb2.toString()); 
    } 
    pw.flush();   
    pw.close(); 

} 
catch (FileNotFoundException e) 
{ 
    System.out.println("File not found."); 
}

来源

2016-09-28 poniboy4

最好是每次调用sort函数时重新初始化dpArr，否则你会对已排序的数组进行“排序”，即什么都不做 –

如果是这样的话那么我不应该得到O（n^2）？ – poniboy4

我真的不明白这个程序是干什么的。你问用户一些数据点，他们输入24601.你生成24601个数据点，然后......用't'这个业务是什么？ 't'是什么意思？您正在对24601个数据点进行1000次排序（但不会像@Lashane指出的那样重新初始化数组），但为什么每次都增加100？你究竟想要测量什么？ – dcsohl

如果你去了你目前的代码，你会看到，第一分选后，你再次使用排序后的数组。那是错的。

要纠正这一点，你可以：

使用一个新的随机排列（如@Lashane建议）;或者，
使用相同的随机数组（即处于与您开始相同的未分类状态）并使用不同的数据透视表;或者，
在每次致电quicksort(dpArr, 0, n - 1);和randomQuicksort(dpArr, 0, n - 1);后洗牌阵列。

我建议最后一个选项会因为你不必担心修改枢轴和你使用相同的值每次运行（而不是它真正的问题在测试分选时间）。要用Java打乱数组，请参阅this question。

来源

2016-09-28 16:50:19 displayName

为什么使用Quicksort获得线性运行时间？

回答

相关问题