算法分析
一、什么是算法分析?
程序和算法的区别。算法是对问题解决的分步描述,程序则是采用某种编程语言实现的算法,同一个算法通过不同的程序员采用不同的编程语言,能产生很多程序。
我们来看一段程序,完成从1到n的累加,输出总和。设置累计变量=0,从1到n循环,逐次累加到累计变量,返回累计变量。
再看第二段程序,是否感觉怪怪的?但实际上本程序功能与前面
那段相同,这段程序失败之处在于:变量命名,有无用的垃圾代码。比较程序的“好坏”,可从多因素入手,如代码风格、可读性等等。
我们主要感兴趣的是算法本身特性,算法分析主要就是从计算资源消耗的角度来评判和比较算法,更高效利用计算资源,或者更少占用资源的算法,就是好算法。从这个角度,前述两段程序实际上是基本相同的,它们都采用了一样的算法来解决累计求和问题。
二、计算资源指标
何为计算资源?一种是算法解决问题过程中需要的存储空间或内存,但存储空间受到问题自身数据规模的变化影响,要区分哪些存储空间是问题本身描述所需,哪些是算法占用不容易。
另一种是算法的执行时间。我们可以对程序进行实际运行测试,获得真实的运行时间。Python有一个time模块,可以获取计算机系统当前时间,在算法开始前和结束后分别记录系统时间,即可得到运行时间。
三、运行时间检测
累计求和程序的运行时间检测,增加了总运行时间,函数返回一个元组tuple:包括累计和,以及运行时间(秒),连续运行5次看看。
如果累加到100000看起来运行时间增加到10000的10倍
进一步累加到1000000运行时间又是100000的10倍了
四、第二种无迭代的累计算法
利用求和公式的无迭代算法,采用同样的方法检测运行时间,需要关注的两点,这种算法的运行时间比前种都短很多,运行时间与累计对象n的大小没有关系(前种算法是倍数增长关系),新算法运行时间几乎与需要累计的数目无关。
五、运行时间检测的分析
观察一下第一种迭代算法,包含了一个循环,可能会执行更多语句。这个循环运行次数跟累加值n有关系,n增加,循环次数也增加。但关于运行时间的实际检测有点问题。同一个算法,采用不同的编程语言编写,放在不同的机器上运行,得到的运行时间会不一样,有时候会大不一样,比如把非迭代算法放在老旧机器上跑,甚至可能慢过新机器上的迭代算法,所以我们需要更好的方法来衡量算法的运行时间,这个指标与具体的机器、程序、运行时段,与编译器都无关。
公众号推荐:数据思践
数据思践公众号记录和分享数据人思考和践行的内容与故事。
《数据科学与人工智能》公众号推荐朋友们学习和使用Python语言,需要加入Python语言群的,请扫码加我个人微信,备注【姓名-Python群】,我诚邀你入群,大家学习和分享。
关于Python语言,有任何问题或者想法,请留言或者加群讨论。