专题

作者：相国大人

联系：sunxiangguodut@qq.com

版权所有，禁止转载

专题 专题一时间复杂度分析 1 普通复杂度函数的增长2 递归与分治的复杂度主定理 专题二求解迷宫问题专题三分治法深入 1 二元搜索问题2 both max and min3 dominating numbers4 max sum two 专题四线性规划专题五贪心算法专题六中位数和顺序统计量专题七散列表专题八红黑树专题九斐波那契堆wenti专题十van Emde Boas树专题十一 网络流专题十二字符串问题专题十三外排序

1. 专题一：时间复杂度分析

1.1 普通复杂度:函数的增长

Θ 记号：

Θ(g(n))={f(n):存在正常量c1,c2和n0,使得对于所有n⩾n0,有0⩽c1g(n)⩽f(n)⩽c2g(n)}

Ω 记号：

Ω(g(n))={f(n):存在正常量c和n0,使得对于所有n⩾n0,有0⩽cg(n)⩽f(n)}

O 记号：

O(g(n))={f(n):存在正常量c和n0,使得对于所有n⩾n0,有0⩽f(n)⩽cg(n)}

1.2 递归与分治的复杂度:主定理

主定理：

对于 T(n)=aT(n/b)+f(n) ,其中 a⩾1,b>1 是常数，我们将 n/b 解释为 ⌊n/b⌋ 或 ⌈n/b⌉ ,则 T(n) 有如下的渐进界：

若对于某个常数 ε>0 ,有 f(n)=O(nlogba−ε) ,则 T(n)=Θ(nlogba) 若 f(n)=Θ(nlogba) ,则 T(n)=Θ(nlogbalgn)=Θ(f(n)lgn) 若对某个常数 ε>0 ，有 f(n)=Ω(nlogba+ε) ,且对某个常数 c<1 和所有足够大的n有 af(n/b)⩽cf(n) ,则 T(n)=Θ(f(n))

练习：

T(n)=9T(n/3)+nlgn

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

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

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

答案：

Θ(n2) ,也可以写成 O(n2)

Θ(lgn)

Θ(nlgn)

Θ(n2lgn)

回顾：堆的维护

def max_heapify(A,current_root): largest=max(current_root.left,current_root,current_root.right) if largest is not current_root: swap(largest,current_root) max_heapify(A,largest)

这段代码的复杂度是多少？

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

根据主定理得到复杂度为 O(lgn)

因此，在优先队列中，如果采用堆来存储，那么函数 extract_min() 的复杂度为 O(lgn)

因此，堆排序的复杂度为 O(nlgn)

判断下面代码的时间复杂度：

快速排序：

def partition(A,p,r) x=A[r] i=p-1 for j=p to r-1 if A[j]<=x i=i+1 swap(A[i],A[j]) swap(A[i+1],A[r]) return i+1 def quick_sort(A,p,r) q=partition(A,p,r) quick_sort(A,p,q-1) quick_sort(A,q+1,r)

显然，第一个函数的代码时间复杂度为 A[p...r] 的长度，即 O(n) ，所以quick_sort()的时间复杂度为：

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

根据主定理， T(n)=Θ(nlgn)

归并排序：

def merge_sort(A[p...r]) mid=(p+r)/2 merge_sort(A[p...mid]) merge_sort(A[mid+1...r]) merge(A[p...mid],A[mid+1...r],C[p...r]) A[p...r]=C[p...r]

merge的复杂度为 O(m1+m2)

所以整体的复杂度为

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

根据主定理， T(n)=Θ(nlgn)

确定下面这个式子的复杂度：

T(n)=2T(n‾‾√)+lgn

解答：

令 n=2k ，并带入原式得：

T(2k)=2T(2k/2)+k

我们令 S(k)=T(2k) ,则有：

S(k)=2S(k/2)+k

根据主定理，有 S(k)=Θ(klgk)

因为 n=2k 所以 k=lgn ，于是得到 T(n)=T(2k)=S(k)=Θ(klgk)=Θ(lgnlglgn)

2. 专题二：求解迷宫问题

待续未完

3. 专题三：分治法深入

分治法是将一个规模为n的问题分解为若干个规模小一些的子问题，然后找出这些字问题或者一部分子问题的解并由此得到原问题的解。在解决这些子问题时，分治法要求用同样的方法递归解出。也就是说，我们必须能把这些子问题用同样的方式再分为更小的问题直至问题的规模小到可以直接解出。这个不断分解的过程看起来很复杂，但用递归的算法表达出来却往往简洁明了。通常，分治法只要讲明三件事即可：

Bottom case:对于足够小的输入规模，如何直接解出Divide：如何将一个规模为n的输入分为整数个规模小一些的字问题Conquer：如何从子问题的解中获得原规模为n的解

3.1 二元搜索问题

假定要在一个已经排好序的数组 A[1...n] 中查找一个数是否等于x，如果有 A[i]=x ，则报告序号 i ，否则报告none,我们可以采用以下的算法：

def binary_search(A,p,r,x) if p>r: return none mid=(p r)/2 if A[mid]=x: return mid elif x<A[mid]: binary_search(A,p,mid-1,x) else: binary_search(A,mid 1,r,x)

(想一想，复杂度是多少？)

3.2 both max and min

Given n numbers stored in A[1..n], we wish to design a divide-and-conquer algorithm that finds both the maximum number and the minimum number in this array.

时间复杂度T(n)=2T(n/2) O(1)

3.3 dominating numbers

3.4 max sum two

4. 专题四：线性规划

待续未完

5. 专题五：贪心算法

待续未完

6. 专题六：中位数和顺序统计量

待续未完

7. 专题七：散列表

待续未完

8. 专题八：红黑树

待续未完

9. 专题九：斐波那契堆wenti

待续未完

10. 专题十：van Emde Boas树

待续未完

11. 专题十一： 网络流

待续未完

12. 专题十二：字符串问题

待续未完

13. 专题十三：外排序

待续未完