对于递归算法例如求阶乘，他们就会呈现出一种线性复杂度

def fact(n):
  if n==1:
      return 1
  else:
     return n*fact(n-1)

上面的算法复杂度就达到了O(n)

对数线性复杂度

很多对数线性复杂度的方法都是归并排序一类

多项式复杂度

有算法随着n的次幂增长

平方级复杂度

复杂度

在这个算法当中出现了两种复杂度，所以我们要舍弃其中一个较小的复杂度，也就是后项的复杂度，进而采用前项的平方复杂度

指数算法

典型例子就是递归算法
比如汉诺塔问题用递归算法来描述仅需要两步就可以完成，但是很不幸的，很多重要的问题恰恰是指数复杂度的，这样的代价非常高昂

def genSubsets(L):
  res=[]
  if len(L)==0:
      return [[]]
  smaller=genSubsets(L[:-1])
  extra=L[-1:]
  new1=[]
  for small in smaller:
      new1.append(small+extra)
  return smaller+new1

首先假设append是常数时间，时间是多少

我们到现在已经看过了一系列的复杂度表示，越往下走算法越复杂，之后会看到的这些复杂度的例子

L9P4

每次将问题一分为二的算法也就是对数复杂度的经典算法，例如我们常见的二分法求平方根的算法就是经典的对数复杂度算法

一个典型的值得思考的问题

我们组织了一场国际象棋巡回赛，参赛人员有n人，（不考虑平局和认输）你该怎么表示为了决胜所需要的比赛次数？

这个问题刚看上去好像是对数复杂度的问题：因为只要把所有的人两两配对进行比赛，如果还假定每次比赛时间是固定的，那么比赛的次数就会比现行地比赛少特别多。

总结一下几种复杂度及其特点

常数复杂度：不随问题规模和输入大小而改变的复杂度
对数复杂度：常见的对数复杂度例如二分查找以及序列索引，随着问题规模增大而增大