自学教程：Python数据结构与算法之算法分析详解

0. 学习目标

我们已经知道算法是具有有限步骤的过程，其最终的目的是为了解决问题，而根据我们的经验，同一个问题的解决方法通常并非唯一。这就产生一个有趣的问题：如何对比用于解决同一问题的不同算法？为了以合理的方式提高程序效率，我们应该知道如何准确评估一个算法的性能。

通过本节学习，应掌握以下内容：

• 了解算法分析的重要性
• 能够熟练使用大O表示法分析算法的时间复杂度
• 掌握空间复杂度分析方法
• 了解 Python 列表和字典常见操作的时间复杂度

1. 算法的设计要求

算法分析的主要目标是从运行时间和内存空间消耗等方面比较算法。

1.1 算法评价的标准

一个好的算法首先应该是“正确”的，其对于每个输入实例均能终止并给出正确的结果，能够正确解决给定的计算问题。此外，还需要考虑以下方面：

• 高效性：执行算法所需要的时间；
• 低存储量：执行算法所耗费的存储空间，其中主要考虑辅助存储空间；
• 可读性：算法应易于理解，易于编码，易于调试等等。

1.2 算法选择的原则

一个算法同时可以满足存储空间小、运行时间短、其它性能也好是很难做到的，很多情况下，我们不得不对性能进行取舍，在实际选择算法时，我们通常遵循以下原则：

• 若该程序使用次数较少，则力求算法简明易懂；
• 对于反复多次使用的程序，应尽可能选用快速的算法；
• 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。

2. 算法效率分析

算法效率分析根据算法执行所需的时间进行分析和比较，这也称为算法的执行时间或运行时间。要衡量算法的执行时间，一个方法就是做基准分析，这是一种事后统计的方法，其使用绝对的时间单位来记录程序计算出结果所消耗的实际时间。在 Python 中，可以使用 time 模块的 time 函数记录程序的开始时间和结束时间，然后计算差值，就可以得到以秒为单位的算法执行时间。

以计算斐波那契数列第 n 项为例(斐波那契数列从第3项开始，每一项都等于前两项之和)，在计算斐波那契数列第 n 项前后调用 time 函数，计算执行时间：

import timedef fibo(n):    start = time.time()    a, b = 1, 1    if n > 2:        for i in range(n-2):            a, b = b, a + b    end = time.time()    running = end-start    return b, runningfor i in range(5):    results = fibo(100000)    print('It takes {:.8f} seconds to calculate the 10000th item of Fibonacci sequence'.format(results[1]))

代码执行结果如下：

It takes 0.08275080 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08277822 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08176851 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08178067 seconds to calculate the 10000th item of Fibonacci sequence

It takes 0.08081150 seconds to calculate the 10000th item of Fibonacci sequence

但是这种方法计算的是执行算法的实际时间，有两个明显的缺陷：1) 必须先运行依据算法编制的程序；2) 依赖于特定的计算机、编译器与编程语言等软硬件环境，容易掩盖算法本身的优劣。因此，我们希望找到一个独立于程序或计算机的指标，以用来比较不同实现下的算法。

2.1 大O表示法

为了摆脱与计算机硬件、软件有关的因素，我们需要一种事前分析估算的方法。可以认为特定算法的“运行工作量”大小取决于问题的规模，或者说，它是问题规模的函数，这时我们就需要量化算法的操作或步骤。一个算法是由控制结构和基本操作构成的，因此可以将算法的执行时间描述成解决问题所需重复执行的基本操作数。需要注意的是，确定合适的基本操作取决于不同的算法。例如在计算斐波那契数列第 n 项时，赋值语句就是一个基本操作，而在计算矩阵乘法时，乘法运算则是其基本操作。

在上一节的 fibo 函数中，整个算法的执行时间与基本操作(赋值)重复执行的次数n 成正比，具体而言是 1 加上 n-2 个赋值语句，如果使用将其定义为函数可以表示为T(n)=n
python实现新年倒计时实例代码
初学者快看，Python下划线的五个作用介绍