两种求和式

循环赛

等价于,如果在一个有n个专家参加的会议中,需要和之间所有人互相握手,需要多少次握手。或者一个含有n个节点的完全图中应该有多少条边,都是一种整体对整体的计数问题。

一种思维是这样的,每一位人都会跟别的人握手,这样就是n*(n-1),然后每个人都握手了两次,所以除以2,n*(n-1)/2,这和(n-1)+(n-2)+...+1是等价的。

淘汰赛

比赛合计为k/2 + k/4 + k/8 + ... + 1,也就是一个等比数列,q=2, a1=1,所以按公式Sn=a1*(1-q^n)/(1-q)计算下来是2^n - 1,但是在这里k和n是不相等的,k是总人数,n是序数,所以要有一个转换关系,查看关系可以知道2^(n-1)=k/2,所以2^n=kn=log2k,代入2^n - 1计算可以得出最后结果是n-1

所以淘汰赛需要n-1场比赛才能最终除冠军以外的所有人都会被淘汰

其实这个比赛可以用带根的完全二叉树结构来表示,所以n相当于树的高度,k相当于当前高度这一层的节点数,当k=0也就是只有一个根节点,k=1也就是高度为1,第二层的时候,这一层节点数为2。同样给定了当层节点总数n,可以得到高度为k=lgn(以2为底)

另一个有意思的假设:人口如果每一代翻一倍,那么如果当代人口结构是由n个人组成的,之前各代人口的数量总和就只是n-1

二分法或者二分搜索法是一个对数级算法

子集和排列组合

k长度的二进制数串可以看成一个完全平衡二叉树,从根节点到叶节点的遍历走向看成一个字符串,根节点只相当于起点,字符串数串的长度k就相当于树的高度,那么其字符可能的数串数量应该等于其叶节点数2^k

子集关系:如果每个比特所表示的是一个对象是否存在于某个k大小的集合中的话,那么每个比特串所表示的就是该集合的2^k个可能子集的某一个。

所以也就是说,对于一个需要检查其输入对象中每个子集的算法,时间复杂度必然是指数级的

伪多项式算法

这些算法的运行时间都是指数级的,但是看上去像是一个多项式时间的算法。比如对于一个某个数是不是质数的问题,直接的解决办法是:

1
2
3
4
def is_prime(n):
for i in range(2, n):
truetrue if n % i == 0: return False
return True

虽然看起来好像是Θ(n)的算法,但是一个问题的规模值包含n,不是说就是等于n,而是用来编码n的比特数,对于这个问题,如果n等于2的某次方,那么需要的比特数就是lgn + 1,比如8,需要4位比特才能表示。如果将问题规模(比特数)设置为k,那么n=2^(k-1),所以时间复杂度就是Θ(2^k),就是一个指数级别的算法。

排列组合

排序问题的本质是顺序问题。这块内容还好印象比较深刻吧,就不多说了。下面摘录下书中所给出的一些有意思的思考角度。

比如n个人要排队看电影,电影院只有k个座位,这样k大小的子集有多少个可能性呢。这种问题潜意识就是{n k},表示组合。书中给的解释如下:首先排在前面的人的可能性是k!种,剩下的人排列可能性为(n-k)!种,总共有n!中可能,所以{n k} = n!/(k!(n-k)!)

公式的含义就是拿全体排队的可能性总数n!去除以累积出来的各种获胜者子集数

递归和递归式

需要找到函数的非递归版本,用来定义递归算法的运行时间复杂度,其实就是要归纳出递推等式,也就是递归关系。

递归式的一般形式:T(n) = a * T(g(n)) + f(n),然后寻找其通用的递归式,然后将右边等式的T(n)或者其他形式变成T(1),就可以得到其时间复杂度。

T(n) = T(n - 1) + n

这个递推关系代表了握手问题,下面是对其的一个推导:

1
2
3
4
T(n) = T(n - 1) + n
T(n) = T(n - 2) + 2n
...
T(n) = T(n - i) + in

所以当n - i = 1时候,即i=n-1时候,T(n) = n(n-1),所以可以得T(n)的时间复杂度是Θ(n^2)

T(n) = 2T(n-1) + 1

这个递推关系代表了汉诺塔问题,下面是对其的一个推导:

1
2
3
4
5
T(n) = 2T(n-1) + 1
T(n) = 2(2T(n-2)+1) + 1
T(n) = 4T(n-2) + 3
...
T(n) = 2^i T(n-i) + 2^i - 1

所以当n-i = 1时候,即i=n-1时候,T(n) = 2^n - 1,所以可以得T(n)的时间复杂度是Θ(2^n)

T(n) = T(n/2) + 1

这个递推关系代表了二分搜索问题,下面是对其的一个推导:

1
2
3
4
T(n) = T(n/2) + 1
T(n) = T(n/4) + 2
...
T(n) = T(n/2^i) + i

所以当n/2^i = 1时候,即i=log2n时候,T(n) = log2n,所以可以得T(n)的时间复杂度是Θ(lgn)

T(n) = T(n/2) + n

这个递推关系代表了随机选择问题,平均情况问题

1
2
3
4
5
T(n) = T(n/2) + n
T(n) = T(n/4) + n/2 + n
...
# 后面相当于一个等比数列,直接求和得2n(1-1/2^i)
T(n) = T(n/2^i) + 2n(1-1/2^i)

所以当n/2^i = 1时候,即i=log2n时候,T(n) = 2n - 2,所以可以得T(n)的时间复杂度是Θ(n)

T(n) = 2T(n/2) + 1

这个递推关系代表了树的遍历问题

1
2
3
4
5
T(n) = 2T(n/2) + 1
T(n) = 2(2T(n/4)+1) + 1
T(n) = 4T(n/4) + 3
...
T(n) = 2^i T(n/2^i) + 2^i - 1

所以当n/2^i = 1时候,即i=log2n时候,T(n) = 2n - 1,所以可以得T(n)的时间复杂度是Θ(n)

T(n) = 2T(n/2) + n

这个递推关系代表了分治法进行排序问题

1
2
3
4
5
T(n) = 2T(n/2) + n
T(n) = 2(2T(n/4)+n/2) + n
T(n) = 4T(n/4) + 2n
...
T(n) = 2^i T(n/2^i) + i*n

所以当n/2^i = 1时候,即i=log2n时候,T(n) = n+nlgn,所以可以得T(n)的时间复杂度是Θ(nlgn)

归纳法证明

对于T(n)=T(n-1)+1,对于T(1)=1,有T(1)<=c成立,假设在T(n-1)上是成立的,即T(n-1)<=c(n-1)成立,那么

1
2
3
4
T(n)=T(n-1)+1
<= c(n-1) + 1
truetrue = cn - c + 1
truetrue <= cn (c>=1)

所以成立

主定理

对于T(n)=aT(n/b)+f(n)

有a重递归调用,对应于树来说就是a个分支,每重处理掉一定比例的数据(数据集的1/b),除了这些递归调用外,算法中还有一个额外的f(n)操作单元。

分配到每层树的每一个节点的问题规模为f(n/b^i),如果要让问题规模为1,那么树的高度就是logbn

树每个内部节点下面都有a个子节点,所有逐层增加之后,节点数只和就不等于n了,按照树高logbn来算,树宽值为a^(logbn),也就是n^(logba),推导如下:

1
2
3
a^(logbn) = (n^(logna))^(logbn)
= n^(logbn * logna)
truetruetruetruetruetruetrue= n^(logba)
  • 大部分操作运行在根节点上

f(n)∈Ω(n^(logba))

af(n/b) <= cf(n),并且f(n)的增长趋势严格快于叶节点数的增长即f(n)∈Ω(n^(logba))

比如对于T(n)=2T(n/3)+n这种情况,a=2,b=3,那么af(n/b)=2n/3是小于n的,并且n^(logba)=n^0.6,反正只要a<b那么结果都是小于1的,所以f(n)∈Ω(n^(logba)),那么就可以说n属于表达式的主导部分了。

  • 大部分时间在叶节点上

f(n)∈O(n^(logba))

将上面的根叶关系翻转一下,就可以得到f(n)∈O(n^(logba)),所以T(n)∈Θ(n^(logba))

所以首先是判断根节点操作是否始终多于叶节点,然后判断f(n)的增长趋势是不是比叶节点数增长的快。

  • 根节点和叶节点操作时间有相同的渐进增长趋势

f(n)∈Θ(n^(logba))

这样就变成了求该树各层操作之和的求和式,可以通过乘以其高度的方式计算总和,T(n)∈Θ(n^(logba) * lgn)

比如T(n)=2T(n/4)+n^0.5a=2,b=4,n^(logba) = n^0.5,树根节点,叶节点以及各层节点的操作时间都等于Θ(n^0.5),所以总的运行时间是T(n)∈Θ(n^(0.5) * lgn)

实践

侏儒排序法

1
2
3
4
5
6
7
8
9
def gnomesort(seq):
i = 0
truetruewhile i < len(seq):
truetrue if i == 0 or seq[i-1] <= seq[i]:
truetruetruetrue i += 1
truetruetrue else:
truetruetruetrue # 这里需要注意,如果找到没有排序的数字,会一直向开始找到一个合适的位置
truetruetruetruetruetrueseq[i], seq[i-1] = seq[i-1], seq[i]
truetruetruetruetruetruei -= 1

那么最坏的情况就是查找并且移动错位元素,也就是当序列是倒序的时候,是最糟糕的情况,那么移动次数是1 + 2 + 3 + ... + n - 1,最好情况是顺序时候,什么也不需要做,那么时间复杂度应该是Ω(n)O(n^2)来表示

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def mergesort(seq):
mid = len(seq) / 2
lft, rgt = seq[:mid], seq[mid:]
truetrueif len(lft) > 1: lft = mergesort(lft)
truetrueif len(rgt) > 1: rgt = mergesort(rgt)
truetrueres = []
truetruewhile lft and rgt:
truetrue if lft[-1] >= rgt[-1]:
truetruetruetrue # 默认移除最后一个元素
truetruetruetrue res.append(lft.pop())
truetruetruetrueelse:
truetruetruetrue res.append(rgt.pop())
truetrue# 由小到大排序
truetrueres.reverse()
truetruereturn (lft or rgt) + res

分析其时间复杂度:输入规模为n,有两重递归调用,每次子问题的规模为n/2,res.reverse()包含了一些操作,时间复杂度为Θ(n),所以递归式为T(n)=2T(n/2)+Θ(n),时间复杂度为Θ(nlgn)

参考自:Python 算法教程Magnus Lie Hetland