gpt4 book ai didi

java - 为什么我使用 Quicksort 获得线性运行时间?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:17:09 27 4
gpt4 key购买 nike

更新:我知道我的问题是什么。我每次都对 10000 个数据点进行排序。每次迭代将花费相同的时间。 t 是我尝试对这些数据点中的 100 个进行排序,然后添加下一个 100 个数据点、排序等等的错误方法。


我试图证明 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.");
}

最佳答案

如果按照当前代码,您会发现在第一次排序之后,您再次使用排序后的数组。这是错误的。

要更正它,您可以:

  • 使用一个新的随机数组(如@Lashane 所建议的);或者,
  • 使用相同的随机数组(即处于与开始时相同的未排序状态)并使用不同的主元;或者,
  • 在每次调用 quicksort(dpArr, 0, n - 1); 后打乱数组和 randomQuicksort(dpArr, 0, n - 1); .

我建议使用最后一个选项,因为您不必担心修改枢轴并且每次运行都使用相同的值(这在排序时间测试中并不重要)。要在 Java 中打乱数组,请参阅 this question .

关于java - 为什么我使用 Quicksort 获得线性运行时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39752950/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com