算法

算法导论笔记

Posted by BUAADreamer on 2021-08-09
Words 2.3k and Reading Time 10 Minutes
Viewed Times

第一部分 基础知识·

循环不变式·

初始化：循环的第一次迭代之前为真

保持：循环的某次迭代之前为真，则在下次迭代之前也为真

终止：循环终止时，不变式提供有用性质，有助于证明算法成立

第四章 分治策略·

归并排序·

最大子数组问题·

将数组切成左右两部分，则最大子数组要么出现在[l,mid]中，要么跨越了mid，要么就在[mid+1,r]中

矩阵乘法的Strassen算法·

https://zhuanlan.zhihu.com/p/78657463

思想：矩阵乘法算法复杂度高，用矩阵加减法代替部分的矩阵乘法运算

从$O(n3)$降到了$O(n{lg7})$，但由于涉及多次浮点数加减乘除，算法稳定性精确度较低。对于n>300时才适用

求解递归式·

递归树，归纳法，主方法

主方法·

$T(n)=aT(n/b)+f(n)$ $a\ge1,b>1,\epsilon>0$

  1. $f(n)=O(n{log_b{a-\epsilon}})\rightarrow T(n)=\Theta(n{log_ba})$

  2. $f(n)=\Theta(n{log_b{a}})\rightarrow T(n)=\Theta(n{log_ba}lgn)$

  3. $f(n)=\Omega(n{log_b{a+\epsilon}})且\exists c\lt1,s.t.\forall n, af(n/b)\leq cf(n)(正则条件)\rightarrow T(n)=\Theta(f(n))$

主定理理解：情况1和3的小于和大于必须是多项式意义的大小关系，即如果没有相差$n^\epsilon$因子，则进入了1和2或者2和3的缝隙

第五章 概率分析与随机算法·

雇用问题·

随机化输入之后复杂度为$O(\ln n)$

随机化序列方法·

PERMUTE-BY-SORTING方法随机化优先级，根据优先级对数组排列

1
2
3
4
5
permutes=[]
for i in range(n):
    permutes.append((A[i],random.randint(0,n*n*n)))
permutes.sort(key=lambda x:x[1])
A=[permutes[i][0] for i in range(n)]

RANDOMIZE-IN-PLACE方法

1
2
3
for i in range(n):
	j=random.randint(i,n-1)
    A[i],A[j]=A[j],A[i]

第二部分 排序与顺序统计量·

第6章 堆排序·

与插入排序一样是原址排序，复杂度与归并排序相当。

堆可以看成一个完全二叉树

最大堆—进行堆排序

最小堆—构造优先队列

MAX-HEAPIFY(A, i)：维护i节点为根的子树的最大堆性质

1
2
3
4
5
6
7
8
9
10
11
n=len(A)
l=i*2
maxi=i
if l<n and A[maxi]<A[l]:
    maxi=l
r=i*2+1
if r<n and A[maxi]<A[r]:
    maxi=r
if i!=maxi:
    A[i],A[maxi]=A[maxi],A[i]
    MAX-HEAPIFY(A, maxi)

BUILD-MAX-HEAP(A)：遍历[length/2,1]调用MAX-HEAPIFY

HEAPSORT(A)：堆排序

1
2
3
4
5
6
BUILD-MAX-HEAP(A)
sz=len(A)
for i in range(len(A),1):
	A[0],A[i]=A[i],A[0]
	sz-=1
	HEAPIFY(A,i)

优先队列·

共享计算机系统的作业调度

MAXIMUM(S):return S[0]

EXTRACT-MAX(x)：删去最大的并维护最大堆

1
2
3
4
5
max=S[0]
S[0]=S[len(S)-1]
del S[len(S)-1]
MAX-HEAPIFY(S,0)
return max

INCREASE-KEY(S,i,k)：增加i位置的元素值到k

1
2
3
4
5
6
if k<S[i]:
    return -1
S[i]=k
while i>=1 and S[i//2]<S[i]:
    S[i],S[i//2]=S[i//2],S[i]
    i=i//2

INSERT(S,x)：新增一个元素

1
2
3
4
import sys
MAX_INT=sys.maxsize
S.append(-MAX_INT)
INCREASE-KEY(S,len(S)-1,x)

第7章 快速排序·

QUICKSORT·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a=[3,4,1,5,2]
def partition(a,l,r):
    #随机化抽样使划分更平衡
    tmp=random.randint(l,r)
    a[tmp],a[r]=a[r],a[tmp]
    #初始化
    x=a[r]
    i=l-1 #i表示左边的区域的最右端
    j=l #j表示右边的区域的最右端
    for j in range(l,r):
        if a[j]<=x:
            i+=1
            a[i],a[j]=a[j],a[i]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1
def quicksort(a,l,r):
    if l<r: #l>=r时直接返回，否则会爆栈
        sep=partition(a,l,r)
        quicksort(a,l,sep-1)
        quicksort(a,sep+1,r)
quicksort(a,0,len(a)-1)
print(a)

只要是常数划分，时间复杂度都是$O(n\lg n)$

随机化划分则算法复杂度为$O(n\lg n)$

第8章 线性时间排序·

决策树模型·

每一层表示不同层级条件分支，叶子节点表示排序后的标号序列

决策树的叶节点数量为l

则对于一个长度为n的排列

$n!\leq l \lt 2^h$

$h>\lg (n!)=\Omega(n\lg n)$​

因此任何排序算法的下界为$O(n\lg n)$

不采用比较方式的排序需要更多空间，但时间复杂度突破了这个瓶颈，以下几个都为$\Theta(n)$

计数排序·

稳定排序：相同数值的两个数排序前后相对次序不变

空间消耗大

1
2
3
4
5
6
7
8
9
10
11
12
13
a=[4,2,3,1,6,8,7,0,9,1,12]
m=max(a)
dic=[0 for i in range(m+1)]
for x in a:
    dic[x]+=1
for i in range(1,len(dic)):
    dic[i]+=dic[i-1]
outLs=[0 for i in range(len(a)+1)]
for i in range(len(a)-1,-1,-1):
    outLs[dic[a[i]]]=a[i]
    dic[a[i]]-=1
del outLs[0]
print(outLs)

基数排序·

早期卡片编程用到

n次循环(i from 1 to n)，每次序列对第i位数按照从小到大排序，最后的顺序就是从小到大

要求对一位数的排序为稳定排序

桶排序·

将[0,1]划分为[0,1/n],[1/n,2/n]…[(n-1)/n,1]区间

每个数都属于一个小区间中，对每个区间内的数建立链表，使用插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
a=[4,2,3,1,6,8,7,0,9,1,12]
m=max(a)+1
n=len(a)
buckets=[[] for i in range(n)]
def insertB(suba,x):
    i=0
    while i<len(suba) and suba[i]<x:
        i+=1
    if i==len(suba):
        suba.append(x)
    elif i==0:
        suba.insert(0,x)
    else:
        suba.insert(i,x)
for x in a:
    pos=int(x*n/m)
    insertB(buckets[pos],x)
outLs=[]
for b in buckets:
    outLs+=b
print(outLs)

第9章 中位数与顺序统计量·

第i个顺序统计量：一个序列中第i小的元素

选择问题·

输入：一个集合A和一个数i

输出：第i个顺序统计量

利用快速排序中的随机划分函数

1
2
3
4
5
6
7
8
9
def randomselect(a,l,r,i):
    q=partition(a,l,r)
    k=q-l+1
    if k==i:
        return q
    elif i<k:
        return randomselect(a,l,q-1,i)
    else:
        return randomselect(a,q+1,r,i-k)

select算法·

https://blog.csdn.net/luoshixian099/article/details/45286303

第三部分 数据结构·

第10章 基本数据结构·

栈：后进先出·

队列：先进先出·

链表·

1
2
3
4
5
class node:
	def __init__(self,val,prev,next):
        self.value = val
        self.prev = prev
        self.next = next

哨兵用一个哨兵对象nil表示NULL

哨兵可以降低常数因子，但占用额外空间比较浪费，一般不用

1
2
L.nil.prev=L.tail
L.nil.next=L.head

有根树的表示·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class treenode:
    def __init__(self,val,p,leftChild,rightChild):
        self.val=val
        self.p=p
        self.leftChild=leftChild
        self.rightChild=rightChild #多叉树用self.childs=childs childs为节点列表

#另一种表示
class treenode:
    def __init__(self,val,p,leftChild,rightSibling):
        self.val=val
        self.p=p
        self.leftChild=leftChild
        self.rightSibling=rightSibling 
        #leftChild-->最左边的孩子
        #rightSibling-->每个节点的靠右的第一个兄弟

第11章 散列表·

直接寻址表·

即数组，根据关键字k直接索引元素

散列表·

根据函数h(k)的值索引元素

冲突解决办法：链接法 开放寻址法

链接法·

假设任何一个给定元素等可能散列到m个槽中任何一个，与其他元素被散列到哪无关，这个假设为简单均匀散列

每个槽对应一个链表，冲突则放在链表中

散列函数·

多数散列函数都假定关键字全域为自然数集N，如果不是自然数集则一般要通过某种方式转换为自然数，比如字符串和Ascii码

除法散列法·

$h(k)=k\ mod\ m$

m一般取不接近2的整数幂的素数

乘法散列法·

$h(k)=\lfloor m((kA)\ mod\ 1)\rfloor$​

其中 $((kA) mod 1)$ ​为取 $kA$​​​ 的小数部分 $0\leq A \leq 1$

由于移位乘法比较简单，A一般取形如$s/2^w$​的一个小数，m一般取2的整数幂

Knuth认为$A=(\sqrt 5 -1)/2=0.6180339887…$比较合适

全域散列法·

随机选择散列函数，使之独立于关键字

开放寻址法·

$h:U\times{0,1…m-1}\rightarrow {0,1…m-1}$

对每一个关键字k，使用开放寻址法的探查序列 $<h(k,0),h(k,1),…,h(k,m-1)>$​ 选择空的槽位

探查方式

  • 线性探查
  • 二次探查
  • 双重散列

完全散列·

二级散列表，每一级都采用全域散列

第12章 二叉搜索树·

在一棵高度h的二叉树上，动态集合上的操作SEARCH/MINIMUM/MAXIMUM/SUCCESSOR/PREDECESSOR/DELETE/INSERT均可以在O(h)内完成

第13章 红黑树·

平衡搜索树

第14章 数据结构的扩张·

扩张数据结构的步骤·

  1. 选择一种基础数据结构
  2. 确定基础数据结构中要维护的附加信息
  3. 检验基础数据结构上的基本修改操作能否维护附加信息
  4. 设计一些新操作

顺序统计树——在红黑树基础上对每个结点增加一个表示子树大小的size变量

区间树——红黑树基础上，关键字采用区间信息和端点最大值

FEATURED TAGS
算法
FRIENDS