O(N log N)复杂度-与线性相似吗? [英] O(N log N) Complexity - Similar to linear?

问题描述

所以我想我会因为提出这样一个琐碎的问题而被埋葬，但是我对某些事情有些困惑.

So I think I'm going to get buried for asking such a trivial question but I'm a little confused about something.

我已经用Java和C实现了快速排序，并且正在做一些基本的比较.该图显示为两条直线，在10万个随机整数上，C比Java对应的C快4ms.

I have implemented quicksort in Java and C and I was doing some basic comparissons. The graph came out as two straight lines, with the C being 4ms faster than the Java counterpart over 100,000 random integers.

我的测试代码可以在这里找到；

The code for my tests can be found here;

Android基准

我不确定(n log n)行是什么样子，但我不认为这是直线.我只是想检查这是否是预期的结果，并且我不应该尝试在我的代码中发现错误.

I wasn't sure what an (n log n) line would look like but I didn't think it would be straight. I just wanted to check that this is the expected result and that I shouldn't try to find an error in my code.

我将公式粘贴到excel中，对于以10为底的基数，这似乎是一条直线，开始时有点扭结.这是因为log(n)和log(n + 1)之差线性增加吗?

I stuck the formula into excel and for base 10 it seems to be a straight line with a kink at the start. Is this because the difference between log(n) and log(n+1) increases linearly?

谢谢

Gav

推荐答案

放大图，您会看到O(n logn)并不是一条直线.但是，是的，它几乎接近线性行为.要知道为什么，只需取几个非常大的对数即可.

Make the graph bigger and you'll see that O(n logn) isn't quite a straight line. But yes, it is pretty near to linear behaviour. To see why, just take the logarithm of a few very large numbers.

例如(以10为底):

log(1000000) = 6
log(1000000000) = 9
…

因此，要对1,000,000个数字进行排序，O(n logn)排序会增加一个可衡量的因子6(或者略微增加一点，因为大多数排序算法将取决于以2为底的对数).不是很多.

So, to sort 1,000,000 numbers, an O(n logn) sorting adds a measly factor 6 (or just a bit more since most sorting algorithms will depend on base 2 logarithms). Not an awful lot.

实际上，该对数因子非常小，对于大多数数量级而言，已建立的O(n logn)算法优于线性时间算法.一个突出的例子是创建后缀数组数据结构.

In fact, this log factor is so extraordinarily small that for most orders of magnitude, established O(n logn) algorithms outperform linear time algorithms. A prominent example is the creation of a suffix array data structure.

最近有一个简单的案例咬伤了我当我尝试通过使用基数改进短字符串的快速排序排序时排序.事实证明，对于短字符串，这种(线性时间)基数排序要比快速排序快，但是对于相对较短的字符串来说还是有一个转折点，因为基数排序主要取决于您排序的字符串的长度.

A simple case has recently bitten me when I tried to improve a quicksort sorting of short strings by employing radix sort. Turns out, for short strings, this (linear time) radix sort was faster than quicksort, but there was a tipping point for still relatively short strings, since radix sort crucially depends on the length of the strings you sort.

这篇关于O(N log N)复杂度-与线性相似吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！