Question

同一问题可用不同算法解决，而一个算法的优劣将直接影响程序的效率和性能。算法的评价主要从时间复杂度和空间复杂度来考虑。空间复杂度的分析相对来说要简单，并且在当前的计算硬件资源发展形势下，对空间复杂度的关注远没有时间复杂度高。因此降低算法的复杂度主要集中在对其时间复杂度的考量，本章侧重考虑时间复杂度。算法的时间复杂度是指算法需要消耗的时间资源，常使用大写字母O表示。如插入排序的时间复杂度为O(n2)，快速排序的最坏运行时间是O(n2)，但是平均运行时间则是O(n log n)。同一算法对应的不同代码实现的性能差异可能仅仅体现在其系数上，但数量级上仍然在同一水平，但不同时间复杂度的算法随着计算规模的扩大带来的性能差别则较为明显。下面是算法时间复杂度大O的排序比较：

O(1)<O(log* n)<O(n)<O(n log n)<O(n ²)<O(c ⁿ)<O(n!)<O(n ⁿ)

因此对算法改进的目的是尽量往时间复杂度较低的O靠近。要降低算法的复杂度，首先要对算法复杂度进行分析。算法分析建立在一定的假设前提上：即一台给定的计算机执行每一条指令的时间是确定的，因此，对于获取字典中某个key对应的值，其时间复杂度为O(1)，查找列表中某个元素，其时间复杂度最优为O(1)，最坏的情况为O(n)。下面的示例中用于求两个列表交集，即使函数中存在条件分支，虽然if部分运算的时间复杂度为O(1)，但else部分需要循环遍历两个列表，其时间复杂度为O(n2)，因此最终的算法复杂度为O(n2)。

def intersection1(list1,list2):
  result = {}
  if len(list1)<5:                  #
时间复杂度为O(1)
      print list1
  else:                         #
时间复杂度为O(n2)
      for item in list1:
          if item in list2:
               result[item] = True
      return result.keys()

需要特别说明，算法的复杂度分析的粒度非常重要，其前提一定是粒度相同的指令执行时间近似，千万不能将任意一行代码直接当做O(1)进行分析。例如上面的例子中如果有其他函数再调用intersection1，纵然在调用函数中只有一行代码，该行代码的时间复杂度仍然要按照O(n2)计算。另外，算法复杂度分析建立在同一级别语言实现的基础上，如果Python代码中含有C实现的代码，千万不能将两者混在一起进行评估。关于更多算法分析的思想和方法，读者可以查看数据结构与算法相关资料。

Python常见数据结构基本操作的时间复杂度如表8-4所示。

表8-4　常见数据结构基本操作的时间复杂度