|||
快速排序去重?计算机专家与程序员的不同
姜咏江
n个数排序算法时间复杂度是多少?一般程序员会脱口而出:O(n!)。这是按照数学家的想法,从小到大,或者从大到小,一一比较得到的算法。如果你是一位计算机专家,不是一般的程序员,就可以用O(n)时间复杂度得出结果。不信?
我要介绍的方法,不仅可以快速排序,而且可以去掉重复的数。
计算机专家要你准备一块足够大的干净存储空间(一般的计算机都可以满足)。计算机专家排序的秘诀就是“将数放到这个数所标志的地址单元”!
实际上,计算机内部并没有一般的实数,只有无符号的二进制整数(更多的请看本人写的《自己设计制作CPU与单片机》第10章),因而你可以将一个数放在这个数标志的存储地点(用指针实现),于是n个数排序算法时间复杂度就从O(n!)转化成O(n)啦。不仅如此,那些重复的数也会剩下唯一的一个了。
此文为2016中国计算机大会P vs.NP论坛准备。
2016-8-1
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-7 07:05
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社