0
更新:我明白我的问题是什么。每次我排序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.");
}
最好是每次调用sort函数时重新初始化dpArr,否则你会对已排序的数组进行“排序”,即什么都不做 –
如果是这样的话那么我不应该得到O(n^2) ? – poniboy4
我真的不明白这个程序是干什么的。你问用户一些数据点,他们输入24601.你生成24601个数据点,然后......用't'这个业务是什么? 't'是什么意思?您正在对24601个数据点进行1000次排序(但不会像@Lashane指出的那样重新初始化数组),但为什么每次都增加100?你究竟想要测量什么? – dcsohl