免费咨询律师的软件_页面设计上下左右如何设置_雅虎日本新闻_今天特大新闻最新消息

chap 2 递归与分治

复杂度递推表达式如何求解

2.1归并排序

2.1.1要点

稳定排序。
先分解，再合并（处理）
可改为自下而上（迭代版本）

缺点：

• ①合并时也要比较、挪动位置——只是渐进意义上的O(n)
• ②空间开销O(n)（本次考试不考察空间复杂度）

以上两个缺点使之不如快排。

2.1.2代码

分：

合：

非递归-分：

2.1.3时间复杂度分析

$T(n)=2T(\frac{n}{2})+O(n)$，即$O(nlogn)$

2.1.5扩展问题：逆序对

问题：给定一个长度为n的排列，求其逆序对数

逆序对： 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 <A[i], A[j]> 称为 A 的一个逆序对.

使用归并排序后时间复杂度为$O(nlogn)$，而朴素算法的复杂度为$O(n^2)$

2.2快速排序

2.2.1要点
不稳定排序

2.2.2代码
外壳：

分区（下标范围：p~r）：

2.2.3时间复杂度分析

最好：$T(n)=2T(\frac{n}{2})+O(n)$，即$O(nlogn)$

不好不坏，每次按比例划分，如1比9： $T(n)=T(\frac{n}{10})+T(\frac{9n}{10})+O(n)$，即$O(nlogn)$

一下好一下坏：$T(n)=2U(\frac{n}{2})+O(n)，U(n)=T(n-1)+O(n)$，即$O(nlogn)$

最坏：$T(n)=T(n-1)+O(n)$，即$O(n^2)$

2.2.4走例子

2.2.5扩展：稳定快排写法

在一次partition中，创建一个临时数组，在要partition的数组里找到小于pivot的元素添加到临时数组中，然后将 pivot添加到临时数组中， 然后再扫描一遍数组将大于等于pivot到元素添加到临时数组中，最后再将临时数组拷贝回原数组，这样partition之后 到快速排序就是稳定的。

分区三趟遍历

代码：

public static int partitionStable(int[] array, int left, int right) {int[] temp = new int[right - left + 1];//制定最左元素为pivotint pivot = array[left];int idxForTemp = 0; // 初始化指向临时数组temp 的第一个位置//先在 left 到right 这个范围内找小于 pivot 到元素for (int i = left + 1; i <= right; i++) {if (array[i] < pivot) {temp[idxForTemp++] = array[i];}}temp[idxForTemp++] = pivot; // 把 pivot放到它该有到位置上面int awsFromTemp = idxForTemp - 1; // 保存放pivot到位置 后面要用//再遍历一遍数组找到所有大于等于pivot到元素 依次放到临时数组temp中for (int i = left + 1; i <= right; i++) {if (array[i] >= pivot) {temp[idxForTemp++] = array[i];}}idxForTemp = 0;int aws = 0;//把排好序到部分拷贝回原数组for (int i = left; i <= right; i++) {if(idxForTemp == awsFromTemp){aws = i;}array[i] = temp[idxForTemp++];}return aws;}

2.3线性时间选择

（没有扩展，难在分组代码）

代码
随机选择：

分组选择：

四个参数的partition函数代码：(已测试)

int Partition(int nums[], int lo, int hi, int X) {for (int i = lo; i < hi; i++) {if (nums[i] == X) {swap(nums[i], nums[lo]);break;}}int i = lo, j = hi - 1;while (i < j) {while (i < j && nums[j] >= X) j--;if (i < j) nums[i++] = nums[j];while (i < j && nums[i] <= X) i++;if (i < j) nums[j--] = nums[i];}nums[i] = X;return i;
}

书上代码的数组下标貌似都是左右闭区间，这不规范。

75和5这两个常数是怎么确定的：

复杂度

随机选择：平均$O(n)$ ,最差$O(n^2)$

分组选择：最差$O(n)$

2.4 二分查找

（扩展：快速幂）

chap 3 动态规划

3.1矩阵连乘

3.1.1最优子结构证明

3.1.2状态转移方程

状态定义：$m[i][j]$ 表示计算从矩阵 $A_i$ 到$A_j$的连乘积的最小标量乘法次数。

状态转移方程：
$$m[i][j]=\underset{i\le k<j}{\min }(m[i][k]+m[k+1][j]+p_{i-1}\cdot p_k\cdot p_j)$$
其中 $p_i$ 是矩阵 $A_i$的行数。

3.1.3代码

3.1.4复杂度

$O(n^3)$

3.1.5走例子

3.1.6扩展

输出具体方案

3.2最长公共子序列

状态定义：$c[i][j]$表示序列$X$的前 $i$ 个元素和序列 $Y$ 的前 $j$个元素的最长公共子序列的长度。

状态转移方程：
$$c[i][j]=\{\begin{array}{ll}c[i-1][j-1]+1& \text{if }{x}_i=y_j\\ \max (c[i-1][j],c[i][j-1])& \text{otherwise}\end{array}$$

（拓展：具体方案，[所有方案？]，最长上升子序列，回文子序列）

具体方案

3.3最大子段和

复杂度O(n)

3.4 01背包(不考优化)

状态定义：$m[i][j]$ 表示考虑第 $i$ 至 $n$ 个物品，在背包容量为 $j$ 时的最大价值。

状态转移方程：
$$m[i][j]=\max (m[i+1][j],m[i+1][j-w[i]]+v[i])$$

chap 4 贪心

贪心策略的正确性证明：只有Dij算法与其他三个不同。

4.1活动安排

贪心策略

按结束时间非递减排序。每次选择与已选活动集相容且结束时间最早的活动。

正确性证明

代码

复杂度

O(nlogn)

4.2最优装载问题

贪心策略：重量最轻者先装。

证明：

代码：

算法主要计算量在排序。复杂度nlogn

4.3单源最短路径

贪心策略：

选V-S中特殊路径长度最短的顶点加入到S中。

证明：

代码：

4.4背包问题

策略：

证明：参考最优装载。形式化证明。

代码：

chap 5 回溯法

5.1 TSP

5.1.1解向量设计

用n元组x[1:n]表示旅行商问题的解。其中，x[i]表示旅行商经过的第i个城市编号为x[i]。

5.1.2剪枝策略

1. 边权=infinity，此路不通，剪
2. 记录之前已经到达了叶子节点的最短路径best。如果当前路径长度已经大于等于best，剪。

5.1.3时间复杂度分析

5.1.4画树

note：

1. 最开始的best=101是随便设的，实际上应为infinity
2. 假设从1出发，就把根节点的其他孩子都剪了
3. 回路应该再回到起始点，比如树上的2-3-4，完整应该是1-2-3-4-1，4-1的路径更新合并到了一步
   

5.1.5 输出结果

（1，3，2，4），最短路程=25

5.2 n皇后

5.2.1 解向量设计
用n元组x[1:n]表示n后问题的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。

5.2.2 剪枝策略
设两个皇后摆放的位置分别是(i, xi)和(j, xj)

1. 由于不允许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。 即$x_i\ne x_j$
2. 由于不允许将2个皇后放在同一斜线上，所以$|i-x_i|\ne |j-x_j|$

5.2.3 时间复杂度分析
$O(n!)$

5.2.4 画树

当n=4时，树如下：

note：在下图中找到一个可行解就停止了

5.2.5 输出结果

（2，4，1，3）

5.3 0-1背包

5.3.1 解向量设计
用n元组x[1:n]表示01背包的解。其中，x[i]取值为1或0，表示第i件物品放入或不放入背包。

5.2.2 剪枝策略

左子树：放不下，剪

右子树：上界小于已得到的最优值，剪

5.2.3 时间复杂度分析

5.2.4 画树

5.4 图的m着色