O(N log N)复杂性 - 与线性相似？
gav*_*gav 75 language-agnostic complexity-theory quicksort
所以我想我会因为提出这样一个微不足道的问题而被埋葬,但我对某些事情感到有些困惑.
我已经在Java和C中实现了quicksort,我正在做一些基本的比较.该图表以两条直线形式出现,其中C比Java对应的快了4ms,超过100,000个随机整数.
我的测试代码可以在这里找到;
我不确定(n log n)线是什么样的,但我不认为它是直的.我只是想检查这是否是预期的结果,我不应该尝试在我的代码中找到错误.
我将公式固定在excel中,对于10号基础,它似乎是一条直线,在开始时有一个扭结.这是因为log(n)和log(n + 1)之间的差异是线性增加的吗？
谢谢,
GAV
Kon*_*lph 78
使图形更大,你会看到O(n logn)不是一条直线.但是,是的,它非常接近线性行为.要了解原因,只需使用几个非常大的数字的对数.
例如(基数10):
log(1000000) = 6
log(1000000000) = 9
…
因此,为了对1,000,000个数字进行排序,O(n logn)排序会增加一个可信因子6(或者更多一点,因为大多数排序算法将取决于基数2对数).不是很多.
事实上,该日志的因素是如此非常小,对于大小的大部分订单,确立为O(n LOGN)算法优于线性时间的算法.一个突出的例子是创建后缀数组数据结构.
当我尝试通过使用基数排序来改进短字符串的快速排序时,一个简单的案例最近让我感到困惑.事实证明,对于短字符串,这个(线性时间)基数排序比快速排序快,但是对于仍然相对较短的字符串存在一个临界点,因为基数排序关键取决于您排序的字符串的长度.
- 汤姆:我不确定你的意思是线性的.通常,排序算法使用O(n ^ 2)排序(例如小部分上的插入排序)来执行相反的操作,因为它们的常数因子非常小,甚至二次运行时也优于nlogn排序.另一方面,introsort使用一种策略来突破过于递归 - 但同样,这并不是线性的,它只是交换了O(n logn)行为的四元最坏情况. (2认同)
gro*_*hog 11
仅供参考,快速排序实际上是O(n ^ 2),但平均情况为O(nlogn)
仅供参考,O(n)和O(nlogn)之间存在很大差异.这就是为什么它不受任何常数O(n)的限制.
有关图形演示,请参阅:
- 这通常是不真实的.Big O表示法通常表示最坏情况的渐近复杂度,并且它表示限制在算法复杂度之上的函数.O(n)不接近O(nlogn),尽管出于实际目的,O(nlogn)相对较好并且不会更差.快速排序的最坏情况表现肯定不是*不常见的事情.如果你不相信我,请尝试对字典中的条目进行快速排序. (12认同)
- a)没有指定,O()通常用于表示*预期*(平均)复杂度.b)O()表示法不包括常数因子,因此O(n)和O(2n)是相同的.由于log(n)几乎是恒定的(对于大数,与n相比),可以说O(n)和O(n log(n))几乎相同.您应该绘制:http://www.wolframalpha.com/input/？i = plot + 7+x%2C + x+log + x+ from+++to +1500 (2认同)