3.6 【实战】初识算法
数据结构和算法是Python程序设计实践的基础。程序能否快速而高效地完成预定的任务，取决于是否选对了算法，而程序是否能清楚而正确地把问题解决，则取决于是否选对了数据，所以通常也可以认为“数据结构加上算法等于可执行程序”。
扫码看教学视频
前面我们也接触了一些简单的算法，但是并没有给出一个明确的算法定义。算法其实可定义为：在有限步骤内解决数学问题的程序。如果把范围局限在计算机领域，我们也可以把算法定义为：为了解决某项工作或者某个问题，所需要的有限数量的机械性或者重复性指令与计算步骤。
算法的种类非常多，但是它们都会有一些共性。如表3-1总结的那样，算法都会有输入的参数或者数据，也都会有一个或者多个结果。从输入参数到输出结果的过程是明确的，在有限的计算步骤后一定会有结果，不能无限循环。优秀的程序员会把算法写得清晰明白，甚至可以用纸和笔计算出答案。
表3-1 算法的必要条件
我们认清了算法的定义和必要条件后，接下来就要思考：该用什么样的方法来表达算法最为合适？其实算法的主要目的在于让人们了解所执行程序的工作流程与步骤，只要能清楚地体现算法的5个必要条件即可，并没有各种形式上的限制，比如下面几种方式都可以来描述算法。
1）一般文字描述。
2）伪代码。
3）表格或者图形。
4）流程图。
5）程序设计语言。
只谈理论过于空洞，下面通过一道题目来体会下算法的魅力。
问题：如果a+b+c=1000，且a^2+b^2=c^2（a，b，c为自然数），如何求出所有a、b、c可能的组合？
例3-20 a2+b2=c2组合
这个程序运行了1285秒，大概21分钟。我们改进一下算法，进行第二次尝试。
例3-21 修改后的a2+b2=c2组合测试
修改后的代码运行只需要16秒。从21分钟缩短到16秒，这种性能上的提升是惊人的。
上面对于同一问题，给出了两种解决算法。在两种算法的实现中，我们都对程序执行的时间进行了测算，发现两段程序执行的时间相差悬殊（1285.898279秒相比于16.417881秒），由此可以得出结论：实现算法程序的执行时间能够直观地体现出算法的效率，即算法的优劣。
程序的运行离不开计算机环境，包括硬件和操作系统。这些客观原因会影响程序运行的速度并反应在程序的执行时间上。影响性能因素有很多，如何才能客观地评判一个算法的优劣呢？
对于算法的时间效率，我们可以用“大O记法”来表示。“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f（n）<=c*g（n），就说函数g是f的一个渐近函数（忽略常数），记为f（n）=O（g（n））。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T（n）=O（g（n）），则称O（g（n））为算法A的渐近时间复杂度，简称时间复杂度，记为T（n）。
前面的数学描述过于专业，通俗点来讲，对算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率“差不多”，都为n2级。
分析算法时，存在几种可能的考虑。
1）算法完成工作最少需要多少基本操作，即最优时间复杂度。
2）算法完成工作最多需要多少基本操作，即最坏时间复杂度。
3）算法完成工作平均需要多少基本操作，即平均时间复杂度。
第一次尝试的算法核心部分时间复杂度为T（n）=O（n*n*n）=O（n3）。
第二次尝试的算法核心部分时间复杂度为T（n）=O（n*n*（1+1））=O（n*n）=O（n2）。
由此可见，我们尝试的第二种算法要比第一种算法的时间复杂度好得多。于是我们可以总结一下计算时间复杂度的几条基本原则。
1）基本操作，即只有常数项，认为其时间复杂度为O（1）。
2）顺序结构，时间复杂度按加法进行计算。
3）循环结构，时间复杂度按乘法进行计算。
4）分支结构，时间复杂度取最大值。
5）判断一个算法的效率时，往往只需要关注操作数量的最高次项，次要项和常数项可以忽略。
6）在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。
数据结构和算法是编程大牛的基本功，绝世高手不是一朝一夕就能练成的，只有循序渐进这一条路，重视积累才有可能登堂入室，从小白变成大牛。