微信号:grzlwx

介绍:光荣之路官方资讯

理论穿肠过,算法在我心——第四篇 枚举思想

2015-07-10 22:03 光荣之路


今天分享一下枚举思想,这种思想也常是码畜,码奴常用的手段,经常遭到码农以上级别的鄙视,枚举思想可以说是在被逼无奈时最后的狂吼。


一: 思想

有时我们解决某个问题时找不到一点规律,此时我们很迷茫,很痛苦,很蛋疼,突然我们灵光一现,发现候选答案的问题规模在百万之内,此时我们就想到了从候选答案中逐一比较,一直找到正确解为止。


二: 条件

前面也说了,枚举是我们在无奈之后的最后一击,那么使用枚举时我们应该尽量遵守下面的两个条件。

① 地球人都不能给我找出此问题的潜在规律。

② 候选答案的集合是一个计算机必须能够承受的。


三:举例

下面是一个填写数字的模板,其中每个字都代表数字中的”0~9“,那么要求我们输入的数字能够满足此模板。

思路:首先拿到这个题,蛋还是比较疼的,因为找不到好的解题思路,仔细想想这属于查找类型的问题,常用的查找也就5种,能适合该问题的查找也就”顺序查找“和”二分查找“,然后仔细看看问题规模最多也就105=100000,其实根据“二分"的思想在这个问题中并不合适,最后只能用“顺序查找“了。



最后我们还是解决了问题,发现其中的时间复杂度达到了O(n5),这个复杂度理论上是让人不能接收的,还好我们的n在10以内,n的每一次的自增对cpu来说都是莫大的伤害。

_______________________________________________


感谢一楼同学的提醒,你的眼睛很犀利,将O(n5)降低到O(n2),这是非常不错的,为你鼓掌一下。

现将你的想法用code实现一下。


(作者:一线码农 来源:http://www.cnblogs.com/huangxincheng/archive/2012/01/07/2315945.html)


一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!

光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499



 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 【原译】自文档化的JavaScript代码的开发方法 ㊙我造啊,我造啊,可是臣妾就是做不到啊! 改变世界的6大计算机实验室 OCR—探寻文字真实的容颜 数字识别,从KNN,LR,SVM,RF到深度学习