CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

快速排序去重?计算机专家与程序员的不同

已有 4543 次阅读 2016-8-1 05:46 |个人分类:P/NP问题|系统分类:科研笔记| 快速排序

快速排序去重?计算机专家与程序员的不同

姜咏江

      n个数排序算法时间复杂度是多少?一般程序员会脱口而出:O(n!)。这是按照数学家的想法,从小到大,或者从大到小,一一比较得到的算法。如果你是一位计算机专家,不是一般的程序员,就可以用O(n)时间复杂度得出结果。不信?

    我要介绍的方法,不仅可以快速排序,而且可以去掉重复的数。

    计算机专家要你准备一块足够大的干净存储空间(一般的计算机都可以满足)。计算机专家排序的秘诀就是“将数放到这个数所标志的地址单元”!

    实际上,计算机内部并没有一般的实数,只有无符号的二进制整数(更多的请看本人写的《自己设计制作CPU与单片机》第10章),因而你可以将一个数放在这个数标志的存储地点(用指针实现),于是n个数排序算法时间复杂度就从O(n!)转化成O(n)啦。不仅如此,那些重复的数也会剩下唯一的一个了。

 

    此文为2016中国计算机大会P vs.NP论坛准备。

 

2016-8-1

 

 



https://blog.sciencenet.cn/blog-340399-993790.html

上一篇:中俄建立军事同盟才能化解美国对中国的这场围剿
下一篇:专家排序法一种新的排序方法
收藏 IP: 120.52.24.*| 热度|

1 管金昱

该博文允许注册用户评论 请点击登录 评论 (9 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-7 07:05

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部