对数的算法时间复杂剧情/图 [英] Log-log plot/graph of algorithm time complexity

问题描述

我只是写了快速和归并排序算法，我想使自己的运行时间与数组的大小双对数曲线图进行排序。

I just wrote the quick and merge sort algorithms and I want to make a log-log plot of their run time vs size of array to sort.

正如我从来没有这样做，我的问题是它的问题，如果我选择任意的号码数组长度（输入大小），或者我应该遵循一个模式（类似10 ^ 3，10 ^ 4，10 ^ 5，等等）？

As I have never done this my question is does it matter if I choose arbitrary numbers for the array length (size of input) or should I follow a pattern (something like 10^3, 10^4, 10^5, etc)?

推荐答案

在一般情况下，你需要选择数组的长度，每个方法，是大到足以显示预期的O（N log n）的或为O（n ^ 2）型行为。

In general, you need to choose array lengths, for each method, that are large enough to display the expected o(n log n) or O(n^2) type behavior.

如果您的n是太小的运行时间可能会被其他的增长率为主，例如算法的运行时间= 1000000 * N + N ^ 2将看起来是〜O（N）对于n＆LT; 1000对于大多数算法的小样本行为意味着你的双对数图最初是弯曲的。

If your n is too small the run time may be dominated by other growth rates, for example an algorithm with run time = 1000000*n + n^2 will look to be ~O(n) for n < 1000. For most algorithms the small n behavior means that your log-log plot will initially be curved.

在另一方面，如果你的n是太大，你的算法可能需要很长时间才能完成。

On the other hand, if your n is too large your algorithm may take too long to complete.

最好的折衷办法可能是开始与小n和时间为N，2N，4N，...，或N，3N，9N，...并不断增加，直到你可以清楚地看到日志数图asymptoting到的直线。

The best compromise may be to start with small n, and time for n, 2n, 4n,..., or n, 3n, 9n,... and keep increasing until you can clearly see the log log plots asymptoting to a straight lines.

这篇关于对数的算法时间复杂剧情/图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！