算法分析

一、什么是算法分析？

 程序和算法的区别。算法是对问题解决的分步描述，程序则是采用某种编程语言实现的算法，同一个算法通过不同的程序员采用不同的编程语言，能产生很多程序。

 我们来看一段程序，完成从1到n的累加，输出总和。设置累计变量=0，从1到n循环，逐次累加到累计变量，返回累计变量。

   再看第二段程序，是否感觉怪怪的？但实际上本程序功能与前面

那段相同，这段程序失败之处在于：变量命名，有无用的垃圾代码。比较程序的“好坏”，可从多因素入手，如代码风格、可读性等等。

 我们主要感兴趣的是算法本身特性，算法分析主要就是从计算资源消耗的角度来评判和比较算法，更高效利用计算资源，或者更少占用资源的算法，就是好算法。从这个角度，前述两段程序实际上是基本相同的，它们都采用了一样的算法来解决累计求和问题。

 

二、计算资源指标

 何为计算资源？一种是算法解决问题过程中需要的存储空间或内存，但存储空间受到问题自身数据规模的变化影响，要区分哪些存储空间是问题本身描述所需，哪些是算法占用不容易。

 另一种是算法的执行时间。我们可以对程序进行实际运行测试，获得真实的运行时间。Python有一个time模块，可以获取计算机系统当前时间，在算法开始前和结束后分别记录系统时间，即可得到运行时间。

三、运行时间检测

 累计求和程序的运行时间检测，增加了总运行时间，函数返回一个元组tuple：包括累计和，以及运行时间（秒），连续运行5次看看。

    如果累加到100000看起来运行时间增加到10000的10倍

    进一步累加到1000000运行时间又是100000的10倍了

四、第二种无迭代的累计算法

 利用求和公式的无迭代算法，采用同样的方法检测运行时间，需要关注的两点，这种算法的运行时间比前种都短很多，运行时间与累计对象n的大小没有关系（前种算法是倍数增长关系），新算法运行时间几乎与需要累计的数目无关。

五、运行时间检测的分析

 观察一下第一种迭代算法，包含了一个循环，可能会执行更多语句。这个循环运行次数跟累加值n有关系，n增加，循环次数也增加。但关于运行时间的实际检测有点问题。同一个算法，采用不同的编程语言编写，放在不同的机器上运行，得到的运行时间会不一样，有时候会大不一样，比如把非迭代算法放在老旧机器上跑，甚至可能慢过新机器上的迭代算法，所以我们需要更好的方法来衡量算法的运行时间，这个指标与具体的机器、程序、运行时段，与编译器都无关。

公众号推荐：数据思践

数据思践公众号记录和分享数据人思考和践行的内容与故事。

《数据科学与人工智能》公众号推荐朋友们学习和使用Python语言，需要加入Python语言群的，请扫码加我个人微信，备注【姓名-Python群】，我诚邀你入群，大家学习和分享。

    关于Python语言，有任何问题或者想法，请留言或者加群讨论。