执行时间和大O计算quicksort
Excecution time and big O calculation quicksort
我正在制作一个包含 10000、20000、40000、80000 和 160000 名学生的列表，并根据他们的成绩对他们进行快速排序（成绩相同的学生将按学号排序）。同时我是运行一个看执行时间的秒表。我正在使用 Sedgewick 他的快速排序：http://algs4.cs.princeton.edu/23quicksort/
当我打印出学生时，他们都得到了完美的排序，但我注意到执行时间有些奇怪：
10000 0.015
20000 0.019
40000 0.096
80000 0.039
160000 0.109
例如 40.000 达到一个高峰，然后以更大的数额再次下降。当 运行 多次测试时，此行为是一致的，有时峰值在 20.000。这是不幸分配这些数量的原因吗？我也很好奇如何通过执行时间计算大O。
我注意到您使用 Java 作为您的编程语言。在 Java 中很难获得可靠的计时数字，因为 JVM 除了 运行ning 代码之外还做了很多工作 - 它会优化代码（通常对代码进行即时编译或优化运行 频繁），执行垃圾收集（这会弄乱时间）等
没有看到你的代码我不能肯定地说什么，但我认为在一个紧密的循环中多次 运行 代码并计算中位数 [=22] 可能是个好主意=]时间。中位数对异常值的敏感度低于均值，并且应该忽略由于垃圾收集等原因导致的任何异常高的 运行 次。您可能还需要考虑研究高质量的 Java 分析器以获得时间估计更准确。
关于你的第二个问题 - 你如何从 运行 时间计算大 O 时间复杂度？ - 答案是这很棘手。您可以通过查看代码如何随时间增长来凭经验估计代码的时间复杂度，通常查看不同大小的 运行 时间之间的比率。有一些工具可以自动为您执行此操作，like this tool for finding empirical computational complexity。不过，您应该小心这些结果，因为它们不一定会给您正确的答案。例如，求解线性程序的单纯形法在最坏情况指数时间内 运行s，但极难触发该行为。仅查看经验行为可能会让您错过这一点。类似地，即使使用随机化，快速排序也会在某些输入上退化为 O(n2)，但很难检测到这一点，除非你 运行 上的算法大量的输入。
我正在制作一个包含 10000、20000、40000、80000 和 160000 名学生的列表，并根据他们的成绩对他们进行快速排序（成绩相同的学生将按学号排序）。同时我是运行一个看执行时间的秒表。我正在使用 Sedgewick 他的快速排序：http://algs4.cs.princeton.edu/23quicksort/
当我打印出学生时，他们都得到了完美的排序，但我注意到执行时间有些奇怪：
10000 0.015
20000 0.019
40000 0.096
80000 0.039
160000 0.109
例如 40.000 达到一个高峰，然后以更大的数额再次下降。当 运行 多次测试时，此行为是一致的，有时峰值在 20.000。这是不幸分配这些数量的原因吗？我也很好奇如何通过执行时间计算大O。
我注意到您使用 Java 作为您的编程语言。在 Java 中很难获得可靠的计时数字，因为 JVM 除了 运行ning 代码之外还做了很多工作 - 它会优化代码（通常对代码进行即时编译或优化运行 频繁），执行垃圾收集（这会弄乱时间）等
没有看到你的代码我不能肯定地说什么，但我认为在一个紧密的循环中多次 运行 代码并计算中位数 [=22] 可能是个好主意=]时间。中位数对异常值的敏感度低于均值，并且应该忽略由于垃圾收集等原因导致的任何异常高的 运行 次。您可能还需要考虑研究高质量的 Java 分析器以获得时间估计更准确。
关于你的第二个问题 - 你如何从 运行 时间计算大 O 时间复杂度？ - 答案是这很棘手。您可以通过查看代码如何随时间增长来凭经验估计代码的时间复杂度，通常查看不同大小的 运行 时间之间的比率。有一些工具可以自动为您执行此操作，like this tool for finding empirical computational complexity。不过，您应该小心这些结果，因为它们不一定会给您正确的答案。例如，求解线性程序的单纯形法在最坏情况指数时间内 运行s，但极难触发该行为。仅查看经验行为可能会让您错过这一点。类似地，即使使用随机化，快速排序也会在某些输入上退化为 O(n2)，但很难检测到这一点，除非你 运行 上的算法大量的输入。