1 python sorting algorithm time-complexity computation-theory
所以我刚刚学会了排序算法的冒泡,合并,插入,排序等等.他们在排序方法上似乎都非常相似,而我们的方法似乎只有很小的变化.那么他们为什么会产生这样不同的排序时间,例如O(n ^ 2)vs O(nlogn)
你看到的"相似性"(？!)是完全虚幻的.
基本的,O(N平方)接近,一遍又一遍地重复他们的工作,没有任何好处,对于"下一步",在"前一步骤"完成的任何工作.所以第一步需要时间与N成比例,第二步需要N-1,依此类推 - 得到的整数之和从1到N与N平方成正比.
例如,在选择排序中,您每次都在寻找I:N部分中的最小元素,其中我首先是0,然后是1,等等.这是(并且必须)通过检查所有这些元素完成的,因为以前没有注意过以后通过任何优势来承担任何较少量的工作.一旦找到最小元素,就将它与第I个元素交换,递增I,然后继续.O(N平方)当然.
先进的O(N log N)方法结构巧妙,可以利用以前步骤中完成的后续工作步骤.与基本方法相比,这种差异是如此普遍和深刻,如果人们无法察觉,那主要是关于一个人的感知敏锐性,而不是关于方法本身:-).
例如,在合并排序中,您在逻辑上将数组拆分为两个部分,0到半长,半长到长.一旦对每一半进行排序(通过相同的方式递归,直到长度足够短),两个半部合并,这本身就是一个线性子步骤.
由于你每次都减半,你显然需要一些与log N成比例的步骤,并且,因为每一步都是O(N),显然你会得到非常理想的O(N log N).
Python的"timsort"是一个"自然的mergesort",即mergesort的一个变种,它被调整为利用数组的已经排序(或反向排序)的部分,它可以快速识别并避免花费任何进一步的工作.这并没有改变大O,因为这是关于最坏的时间 - 但预期的时间会进一步崩溃,因为在如此多的现实案例中,存在一些部分排序.
(注意,按照big-O的严格定义,quicksort根本不是快速的 - 它的最坏情况与N平方成正比,当你碰巧每次都选择一个可怕的支点时...... 预期 -时间紧迫它很好,虽然没有蒂姆索特那么好,因为在现实生活中你反复挑选灾难支点的情况非常罕见......但是,最坏的情况,它们可能会发生! - ).
timsort是这么好吹走即使是非常有经验的程序员.我不算数,因为我是发明家朋友蒂姆彼得斯和Python狂热分子的朋友,所以我的偏见显而易见.但是,考虑......
...我记得谷歌正在举办一场"技术讲座".坐在我前排的是Josh Bloch,当时也是一名Google员工和Java专家.谈到谈话的中途,他无法抗拒 - 他打开笔记本电脑并开始黑客攻击,看看它是否可能像优秀的,尖锐的技术演示一样好.
因此,timsort现在也是最近发布的Java虚拟机(JVM)中的排序算法,尽管只针对用户定义的对象(基元数组仍旧按旧方式排序,quickersort [*]我相信 - 我不喜欢我不知道哪种Java特性决定了这种"分裂"的设计选择,我的Java-fu相当弱:-).
[*]这实际上是快速排序加上一些针对枢轴选择的黑客,试图避免毒药案例 - 而且这也是Python在蒂姆·彼得斯在几十年来所做的许多重要贡献中给予这一不朽贡献之前使用过的东西.
对于具有CS背景的人来说,结果有时令人惊讶(像Tim,我有幸拥有远在学术背景,而不是在CS,但在EE,这有很大帮助:-).例如,假设您必须维护一个始终在任何时间点排序的不断增长的数组,因为必须将新的传入数据点添加到数组中.
经典方法将使用二分O(log N)为每个新的传入数据点找到正确的插入点 - 但是,为了将新数据放在正确的位置,您需要将其后面的数据移动一个槽,那是O(N).
使用timsort,您只需将新数据点附加到数组,然后对数组进行排序 - 在这种情况下,这是对于Timsort的O(N)(因为它在利用第一批N-1项的已经排序的特性方面非常棒! - ).
您可以将timsort视为将"利用以前完成的工作"推向一个新的极端 - 不仅先前由算法本身完成的工作,而且还有现实数据处理的其他方面的其他影响(导致段到提前排序),都被利用到了剑柄.
然后我们可以进入铲斗排序和基数排序,它改变了话语平面 - 在传统的排序中限制了一个能够比较两个项目 - 通过利用项目的内部结构.
或者类似的例子 - 由Bentley在其不朽的书"Programming Pearls"中提出 - 需要对几百万个唯一正整数的数组进行排序,每个正整数被限制为24位长.
他用一个16M位的辅助数组解决了它 - 毕竟只有2M字节 - 最初是全零:一个通过输入数组来设置辅助数组中的相应位,然后一个通过辅助数组形成所需的再次找到1s的整数- 并且爆炸,O(N)[并且非常迅速:-)]为这个特殊但重要的情况排序! - )