数据结构与算法:(一)绪论
该系列为清华邓俊辉老师数据结构mooc课程总结,向邓老师致敬!
文章目录
一、计算工具,计算算法,计算优劣
-
eg:计算工具:尺规工具
计算=信息处理 计算模型=计算机=信息处理工具 -
冒泡排序:借助sorted标志 ,可提前退出
void bubblesort1A(int A[], int n) {
bool sorted = false; //首先假定尚未排序
while (!sorted) {
sorted = true; ?//假定已经排序
for (int i = 1; i < n; i++) {
if (A[i - 1] > A[i]) {
swap(A[i - 1], A[i]);
sorted = false; //因整体排序不能保证,清楚排序标志
}
}
n--; //可以缩短待排序序列的有效长度
}
}
- 算法:特定模型下,旨在解决特定问题的指令序列
输入, 输出, 确定性, 单调性, 有穷性 - 核心内容
1 各数据结构的ADT接口及其不同实现
(1)序列(向量,列表,栈,队列)
(2)树及搜索树(AVL树,伸展树,红黑树,B-树,kd-树)
(3)优先队列(堆)
(4)字典(散列表,跳转表)
(5)图的算法与应用
2 构造有效算法模块的常用技巧
(1)顺序与二分查找(2)选取与排序(3)遍历(4)模式匹配(5)散列(6)几何查找
3 算法设计的典型策略与模式
(1)迭代(2)贪心(3)递归(4)分治(5)减治(6)试探-剪枝-回溯(7)动态规划
4 复杂度分析的基本方法
(1)渐进分析与相关记号(2)递推关系(3)递推跟踪(4)分摊分析(5)后向分析
二、复杂度度量
-
算法分析主要关注:正确+成本
-
时间复杂度T(n);特定算法处理规模为n的问题所需的时间,关注最坏情况
-
渐进复杂度(渐进上界):大O记号
-
空间复杂度:算法所需存储空间的多少,不计入原始输入所占用的空间
三、渐进分析
- O(1) 常数 效率最高
- O(logn) 常底数,常数次幂无所谓 非常有效
- 多项式复杂度,在实际应用中认为是可接受的 O(n^{c} )
- 指数,不可忍受O(2^{n} )
- 层次级别
四、算法分析
- 两个主要任务:正确性(不变性+单调性)+复杂度
- 复杂度分析的主要方法
(1)迭代:级数求和
(2)递归:递归跟踪+递推方程
(3)猜测+验证 - 级数
- 算法分析:迭代
五、递归
迭代乃人工,递归方神通
1线性递归:减而治之
- 减而治之
- 举例:计算任意n个整数之和
int sum(int A[], int n) {
if (n < 1) return 0; //递归基
else
return sum(A, n - 1) + A[n - 1]; //递归:前n-1项和,再累计第n-1项
}
2二分递归:分而治之
- 分而治之
- Example: 求数组所有元素之和
- Example: MAX2,二分递归从数组区间 A[lo,hi] 中找出最大的两个整数。
void max2(int A[], int lo, int hi, int & x1, int & x2)
{
// 递归基, 总共只有 2个/3个 元素
if (lo + 2 == hi) {* ... * ; return;}
if (lo + 3 == hi) {* ... * ; return;}
// 递归过程,分为两组,两边至少2个元素
int mi = (lo + hi)/2;
// 递归
int x1L, x2L;
max2(A, lo, mi, x1L, x2L);
int x1R, x2R;
max2(A, mi, hi, x1R, x2R);
// 每个递归实例所需操作
if (A[x1L] > A[x1R])
{
x1 = x1L;
x2 = (A[x2L] > A[x1R]) ? x2L : x1R;
}
else
{
x1 = x1R;
x2 = (A[x1L] > A[x2R]) ? x1L : x2R;
}
}
六、 主定理
七、动态规划
举例: Fibonacci数列
为使分治策略有效,必须要保证子问题之间相互独立,即各子问题可独立求解,而无需借助其他子问题的原始数据或者中间结果
递归版不能用!
解决方法
具体代码
int fib (int n) {
int f = 1, g = 0; // fib(-1), fib(0)
while (n-->0) {
g = f + g;
f = g - f;
}
return g;
}
实例:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。
变化:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级…它也可以跳上n级。此时该青蛙跳上一个n级的台阶总共有多少种跳法?
分析:
int jumpFloorII (int number) {
if (number == 0)
return 0;
int f = 1; // fib(1)
for (int i=1; i<number; i++)
f *= 2;
return f;
}
举例:最长公共子序列
递推公式:用 C[i,j]来表示表格中 [Ai,Bj] 处的长度。
参考:https://blog.csdn.net/hrn1216/article/details/51534607
int lcs (string a, string b){
int l1 = a.size();
int l2 = b.size();
int DP[l1+1][l2+1];
memset(DP, 0, sizeof(DP));
for(int i = 1; i <= l1; i++)
for(int j = 1; j <= l2; j++)
if(a[i - 1] == b[j - 1])
DP[i][j] = DP[i - 1][j - 1] + 1;
else
DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]);
return DP[l1][l2];
}
leetcode 300. Longest increasing sequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:Input: [10,9,2,5,3,7,101,18] Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4
参考: https://panxiaoxie.cn/
动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题。
“对于 longest increasing subsequence 里面就存在最优子问题。对于一个序列,每增加一个元素,都可以看作一个子问题。 子问题的解是固定的,但是子问题与当前步的结合又是动态变化的。比如这里,当前 i 位置的值大于 j 的值和小于 j 的值的处理方式就不太一样。我们要做的就是找出这个规律 (递推公式),然后根据填写好的子问题的解的表格,进一步扩大问题规模。”
Optimal Substructure: 设 arr[0…n-1] 为输入数组,L[i]是在第i个位置结束的增加子序列
则L(i) 可以递归的表达: L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or L(i) = 1, if no such j exists. 最终返回 max(L(i)) where 0 < i < n.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
int dp[nums.size()];
dp[0] = 1;
for (int i=1; i< nums.size(); i++){
dp[i] = 1;
for (int j=0; j < i; j++){
if (nums[i] > nums[j] && dp[i] < dp[j]+1){
dp[i] = dp[j] + 1;
}
}
}
return *max_element(dp, dp+nums.size());
}
};
八、三步旋转法与随机打乱
- 三步旋转法
- 随机打乱