算法设计：

算法设计绪论

时间复杂度影响因素

问题规模n，输入序列I，算法本身A

时间复杂度排序

$O(1)<O(logn)<O(n)<O(n²)<O(2^n)<O(n!)<O(n^n)$$O(1)<O(logn)<O(n)<O(n²)<O(2^n)<O(n!)<O(n^n)$

渐进复杂性

求算法渐进复杂性，使算法运行时间T(n)存在T'(n)满足$lim\frac{T(n)-T^{\prime }(n)}{T(n)}=0$$lim\frac{T(n)-T'(n)}{T(n)}=0$，则$T^{\prime }n$$T'n$为渐进复杂性。

结论

渐进复杂性&渐进上界&渐进下界&渐进精确：最高次项 上/下界：所有普通项升为最高次项/只保留最高次项

渐进记号O计算：常系数去掉，相加取最大，乘积找最大

分治-分而治之

分治主方法

主方法适用递归方程形式：$T(n)=aT(\frac{n}{b})+f(n)$$T(n)=aT(\frac{n}b)+f(n)$

主方法的两个量

主方法题解口诀：谁大取谁，相等乘$logn$$log\space n$

分治基本思想

将一个规模为n的问题分解为k个规模为较小的子问题，这些子问题互相独立且与原问题相同。递归地求解这些子问题，然后利用子问题的解合并(构造)出原问题的解

分治算法与递归公式:$T(n)=aT(\frac{n}{b})+f(n)$$T(n)=aT(\frac{n}b)+f(n)$

原问题规模n 子问题规模$\frac{n}{b}$$\frac n b$

分治算法步骤：分解 递归 合并

分治算法案例

前置内容：线性运算的复杂度为$O(n)$$O(n)$

大整数乘法

给定两个都是$2^k$$2^k$位的大整数A、B，求A与B的乘积

推广：用分治法求两个十进制都是n位的A与B的乘积

例:1024和2048分解成如下:

A B

$10\ast {10}^{4/2}+24$$10*10^{4/2}+24$

C D

$20\ast {10}^{4/2}+48$$20*10^{4/2}+48$

$T(n)=4T(\frac{n}{2})+\theta (n)$$T(n)=4T(\frac{n}2)+\theta(n)$

$\text{主}\text{方}\text{法}\text{求}\text{解}\text{得}\text{出}T(n)=\theta (n^2),\text{满}\text{足}T(n)=n^{lo{g}_{b}a}$$主方法求解得出T(n)=\theta(n^2),满足T(n)=n^{log_{b}a}$

二分查找

前提->线性表中的记录必须已按关键字值有序排列(一般情况下视为递增排列)

二分查找的方法：每次循环k都与R的中间元素的关键字(R[min].key)比较

• k==R[mid].key >查找成功

• k<R[mid].key >下次在mid之前(mid-1)继续二分查找

• k>R[mid].key >下次从mid之后(mid+1)继续二分查找

在关键字有序序列(2,3,10,15,20,25,28,29,30,35,40)中采用二分查找法查找关键字为15的元素

第一次查找(0-10)-> 15<R[5].key ->下次去(low-4)查找 >high=mid-1;

第二次查找(0-4)-> 15>R[2].key ->下次去(3-high)查找 >low=mid+1;

第三次查找(3-4)-> 15== R[3].key ->查找成功，关键字比较次数为3

查找失败条件-> high< low

逻辑表达如下:

k==R[mid].key ->查找成功，返回当前元素的逻辑序号->return mid+1;

k < R[mid].key ->下次去(low至mid-1)递归查找k

k > R[mid].key ->下次去(mid+1至high)递归查找k

16
1
int binsearch(int array[],int low,int high,int k){
2
    if(low>high){
3
        return -1;
4
    }
5
    int mid=(low+high)/2;
6
    //查找左边部分
7
    if(k==array[mid]){
8
        return mid+1;
9
    }
10
    if(k>array[mid]){
11
        return binsearch(array,mid+1,high,k);
12
    }
13
    if (k<array[mid]){
14
        return binsearch(array,low,mid-1,k);
15
    }
16
}

二叉树表达二分查找过程

二分查找最优$\theta (1)$$\theta (1)$ 最坏$O(logn)$$O(logn)$

归并排序

举例:一个表中有8个元素，其关键字分别为(6,8,7,9,0,1,3,2)

说明采用二路归并排序方法进行排序的过程

• 创建临时空间保存归并后序列：临时序列长度等于参与排序的序列长度（high-low+1）

• 使用i和j遍历前后子序列，使用k遍历临时序列，比较前后序列的关键字大小

  • 初始位置：i和j分别位于前后序列起始位置 -> i=low, j=mid+1, k=0

  • 前序列的值更小（R[i].key <= R[j].key） -> 将R[i]复制到临时序列中，i和k向后移动

  • 后序列的值更小（R[i].key > R[j].key） -> 将R[j]复制到临时序列中，j和k向后移动

  • 循环结束：i和j其中有一个到达终点 -> i>mid 或 j>high

$\text{根}\text{据}\text{主}\text{方}\text{法}\text{可}\text{得}T(n)=2T(\frac{n}{2})+\theta (n),T(n)=nlogn$$根据主方法可得T(n)=2T(\frac n2)+\theta(n),T(n)=nlogn$

代码逻辑:

26
1
void Merge(int array[], int low, int high, int mid) {
2
    int temparray[high - low + 1];
3
    int n = low, m = mid + 1, k = 0;
4

5
    // 前序列值小于后序列情况，实际上就是谁小谁先进栈
6
    while (n <= mid && m <= high) {
7
        if (array[n] <= array[m]) {
8
            temparray[k++] = array[n++];
9
        } else { // 前序列值大于后序列情况
10
            temparray[k++] = array[m++];
11
        }
12
    }
13

14
    // 剩余元素直接写入临时数组
15
    while (n <= mid) {
16
        temparray[k++] = array[n++];
17
    }
18
    while (m <= high) {
19
        temparray[k++] = array[m++];
20
    }
21

22
    // 将合并后的数组复制回原数组
23
    for (int i = low; i <= high; i++) {
24
        array[i] = temparray[i - low];
25
    }
26
}

快速排序

开始时将序列首元素定位基准，通过快速排序将表一分为二，关键字小于基准值的放置在基准元素前，大于基准值的放置在基准元素后

时间复杂度的分析:

最坏$O(n^2)$$O(n^2)$最好$O(nlogn)$$O(nlogn)$平均$O(nlogn)$$O(nlogn)$

循环赛日程表

循环赛日程表简述:设有$n=2^k$$n=2^k$个运动员要进行循环赛，现要设计一个满足以下要求的比赛日程表:

(1)每个选手必须与其它$n-1$$n-1$个选手各赛一次;(2)每个选手一天只能比赛一次;(3)循环赛一共需要进行$n-1$$n-1$天。

举例:有n=4个运动员要进行循环赛，现要设计一个满足以下要求的比赛日程表(1)每个选手必须与其它4-1个选手各赛一次:(2)每个选手一天只能比赛一次;(3)循环赛一共需要进行4-1天。

例子:分解前:1个4阶表格 分解后:4个2阶表格

推广:分解前:1个n阶表格 分解后:4个$\frac{n}{2}$$\frac n 2$阶表格

对角线相同最后矩阵变为2个不相同的表,所以$T(n)=2T^{\prime }(\frac{n}{2})+f(n)$$T(n)=2T'(\frac n2)+f(n)$

时间复杂度:$\theta (n^2)$$\theta(n^2)$

24
1
int a[10][10];
2
int GameTable(int n,int k){
3
    if(n == 2){ //子问题足够小时
4
        a[k][0]= k+1;
5
        a[k][1]= k+2;
6
        a[k+1][0]= k+2;
7
        a[k+1][1]= k+1;
8
    } else {
9
        GameTable(n/2,k);
10
        GameTable(n/2,k+n/2);
11
        for(int i = k;i<k+n/2;i++){ //填充右上角
12
            for(int j = n/2; j < n; j++){
13
                a[i][j]= a[i+n/2][j-n/2];
14
            }
15
        }
16
    }
17
    //划分子问题
18
    for(int i= k+n/2;i< k+n; i++){
19
         //填充的右下角
20
         for(int j = n/2;j < n; j++){
21
            a[i][j]= a[i-n/2][j-n/2];
22
        }
23
    }
24
}

部分快速排序--第k小元素

30
1
输入：arr[]，整数 l，整数 r，整数 k
2
输出：arr[k]
3

4
函数 partition(arr[], l, r)
5
    int m <- arr[r]  // 选择最后一个元素作为基准
6
    int i <- l
7
    for j <- l to r - 1
8
        if arr[j] < m
9
            交换(arr[i], arr[j])
10
            i <- i + 1
11
        endif
12
    endfor
13
    交换(arr[i], arr[r])  // 将基准放到正确的位置
14
    返回 i  // 返回基准的位置
15

16
函数 quickSelect(arr[], l, r, k)
17
    if l = r
18
        返回 arr[l]  // 如果只有一个元素，直接返回该元素
19
    endif
20
    int pivotIndex <- partition(arr, l, r)  // 对数组进行划分
21
    if k = pivotIndex
22
        返回 arr[k]  // 如果基准位置正好是 k，返回该元素
23
    else if k < pivotIndex
24
        返回 quickSelect(arr, l, pivotIndex - 1, k)  // 在左半部分继续查找
25
    else
26
        返回 quickSelect(arr, pivotIndex + 1, r, k)  // 在右半部分继续查找
27
    endif
28

29
// 调用函数
30
返回 quickSelect(arr, l, r, k)

回溯法-回而溯之

深度优先遍历(DFS)

过程：从无向图中初始顶点v出发，先访问初始顶点v选择一个与顶点v相邻且没被访问过的顶点w，再从顶点w进行深度优先遍历，直到图中与顶点v邻接的所有顶点都被访问过为止

xxxxxxxxxx
10
1
DFS(args){
2
    if(终止条件){
3
        存放结果;
4
        return;
5
    }for(选择节点){
6
        处理节点;
7
        DFS(图,选择的节点);
8
        回溯：撤销处理结果;
9
    }
10
}

$\text{时}\text{间}\text{复}\text{杂}\text{度}:O(n+e)$$时间复杂度:O(n+e)$

其中n为顶点个数,e为边数。

n皇后问题

广度优先遍历（BFS）

过程：访问初始点v，接着访问v的所有未被访问过的邻接点$v_1,v_2,...v_t$$v_1,v_2,...v_t$

按照$v_1,v_2,...v_t$$v_1,v_2,...v_t$的顺序访问每个顶点的所有未被访问过的邻接点

依次类推，直到图中所有和初始点v有路径相通的顶点都被访问过为止

按照层级划分

贪心算法-贪心不足

贪心基本思想

从问题的某一个初始解出发，在每一个阶段都根据贪心策略来做出当前最优的决策，逐步逼近给定的目标，尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，算法终止

贪心特点

每个阶段面临选择时,贪心算法都做出对当前来讲是最有利的选择。

算法简单，选择一旦做出不可更改，即不允许回溯

根据贪心策略来逐步构造问题的解

贪心算法效率高，但不稳定（不能求得最优解）

贪心四步

分解:将原问题分解为若干个相互独立的阶段

解决:对于每个阶段依据贪心策略进行贪心选择，求出局部最优解

合井:将各个阶段的解合并为原问题的一个可行解

证明:证明算法的正确性

贪心选择性质、最优子结构性质

贪心题解

背包问题

物品可以分割

$\begin{array}{c}\text{背}\text{包}\text{问}\text{题}\text{简}\text{述}:\text{有}1\text{个}\text{背}\text{包}，\text{背}\text{包}\text{的}\text{容}\text{量}\text{为}W。\text{有}n\text{个}\text{物}\text{品}\text{对}\text{物}\text{品}i，\\ \text{其}\text{价}\text{值}\text{为}{v}_i，\text{重}\text{量}\text{为}{w}_i。\text{如}\text{何}\text{选}\text{取}\text{物}\text{品}\text{装}\text{入}\text{背}\text{包}，\\ \text{使}\text{背}\text{包}\text{中}\text{所}\text{装}\text{入}\text{的}\text{物}\text{品}\text{的}\text{总}\text{价}\text{值}\text{最}\text{大}?\end{array}$$背包问题简述:有1个背包，背包的容量为W。有n个物品对物品i，\\其价值为v_i，重量为w_i。如何选取物品装入背包，\\使背包中所装入的物品的总价值最大?$

$\frac{\text{价}\text{值}}{\text{重}\text{量}}$$\frac{价值} {重量}$大的优先装入

会场安排问题

会场安排问题简述:设有n个活动的集合C={1,2..,n}，1个资源(如会议室)，而在同一时间内只能有一个活动使用该资源。活动i(i=1,2...,n)的开始时$s_i$$s_i$;，结束时间$f_i$$f_i$,，且$s_i<f_i$$s_i<f_i$,。活动i占用会议室的时间段为半开区间[$s_i$$s_i$,$s_i$$s_i$)。如果[$s_i$$s_i$,$s_i$$s_i$)与[$s_i$$s_i$,f;$s_i$$s_i$)不相交，则称活动i与活动i是相容的。活动安排问题要求在所给的活动集合中选出最大的相容活动子集,也即尽可能地选择更多的活动来使用资源

用结束时间最早

$\begin{array}{c}\text{对}\text{选}\text{择}\text{活}\text{动}\text{操}\text{作}，\text{时}\text{间}\text{消}\text{耗}O(n)\text{对}\text{活}\text{动}\text{结}\text{束}\text{时}\text{间}\text{升}\text{序}\text{排}\text{序}，\\ \text{默}\text{认}\text{使}\text{用}\text{堆}\text{排}\text{序}，\text{时}\text{间}\text{消}\text{耗}O(nlogn)\end{array}$$对选择活动操作，时间消耗O(n)对活动结束时间升序排序，\\默认使用堆排序，时间消耗O(nlogn)$

时间复杂度为$O(nlogn)$$O(nlogn)$

Prim算法

Kruskal算法

总结

算法思想：

普里姆(Prim)算法->每次循环选择一个合适的顶点（稠密图）

克鲁斯卡尔(Kruskal)算法->每次循环选择一条合适的边（稀疏图） 时间复杂度：

普里姆(Prim)算法 每次循环需要在所有的U中顶点和V-U中顶点的边选取权值最小的边

时间复杂度 ->$O(n^2)$$O(n^2)$->只与顶点数n有关

克鲁斯卡尔(Kruskal)算法 每次循环需要在剩余的边中选取权值最小的边

时间复杂度 ->$O(eloge)$$O(eloge)$->只与边数e有关 适用范围 普里姆(Prim)算法 ->稠密图

克鲁斯卡尔(Kruskal)算法 ->稀疏图

Dijkstra算法

动态规划

动态规划的特点

常用情况

主要用于求解以时间划分阶段的动态过程的优化问题,动态规划算法通常用于求解具有某种最优性质的问题

基本思想

经分解得到的各个子问题往往不是相互独立的

在求解过程中，将已解决的子问题的最优值进行保存，在需要时可以轻松取出

Dynamic Programming

1. 确定dp数组（dp table）以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

递推公式很多时候决定了dp数组如何初始化

遍历对dp递推公式进行

动态规划题解

矩阵连乘

$A_1,A_2$$A_1,A_2$矩阵相乘次数 = $A_1$$A_1$的行数$\times$$\times$$A_1$$A_1$的列数$\times$$\times$$A_2$$A_2$的列数

= $A_1$$A_1$的行数$\times$$\times$$A_2$$A_2$的行数$\times$$\times$$A_2$$A_2$的列数

两个矩阵相乘取第一矩阵的行第二矩阵的列

如:$A_1(5\ast 7),A_2(7\ast 10),A_3(10\ast 3)$$A_1(5*7),A_2(7*10),A_3(10*3)$

$\begin{array}{c}{A}_1|A_2{A}_3=>A_2{A}_3=7\ast 10\ast 3=210\\ ->(7\ast 3)A_1=(7\ast 3)\ast (5\ast 7)=147\\ total:357\end{array}$$A_1|A_2A_3 => A_2A_3=7*10*3=210\\->(7*3)A_1=(7*3)*(5*7)=147\\total:357$

$\begin{array}{c}{A}_1{A}_2|A_3=>A_1{A}_2=5\ast 7\ast 10=350\\ ->(5\ast 10)A_3=(5\ast 10)\ast (10\ast 3)=150\\ total:500\end{array}$$A_1A_2|A_3=>A_1A_2=5*7*10=350\\->(5*10)A_3=(5*10)*(10*3)=150\\total:500$

最优解为357次

最长公共子序列

方法:

1.比较字符异同 异:看左看上取最大;同:看左上角+1重复直到表格填完

2.比较字符异同 比较xy字符(异:看左/上数字大小|同:先保存走左上);谁大往谁走,相同一起走;直到边缘