算法设计与分析期末复习

[QiYongchuan]

[QiYongchuan]

0.基础知识补充部分

ps：不是针对具体哪个考试题，直接针对做题的，仅是用来学习一些基本的概念补充

0.1 时间复杂度计算

注：区别在于常数阶的size是输入确定好的值，而线性阶是可以一直增加的。

来源：hello 算法

[QiYongchuan]

一、分治法

涉及到的算法：二分搜索、合并排序、快速排序

例子：把作业分成一个一个的小部分，一个人做一部分？然后再整合到一块。

思想： 分(Divide)，治(Conquer)，合(Combine)。

（1）分解成若干个规模较小、相互独立、类型相同的子问题 （2）子问题足够小时，直接分解 （3）子问题的解，组合成原问题

最大字段和问题

1. 枚举法解决问题

2. 分治法解决方案

3. 动态规划解决方案

问题描述： 当所有整数都是负数时，记为0 当（a1,a2,a3,a4,a5,a6)=(-2,11--4,13,-5,-2)时，最大字段和

1.枚举法（蛮力、暴力、穷举)

穷举法就是将n中所有的字段组合找出来，比较字段的和的大小，选出最大的来。

枚举法的优化：可将复杂度降为n²

2.分治法求最大字段和

代码部分：

来源：算法设计与分析MOOC-青岛大学-张公敬教授

注意：这里的left和right是数组的两个端点，区分lefts和rights数组的和

3.动态规划法求最大字段和

【北大公开课】 算法设计与分析 屈婉玲教授 （76p）

老师讲义：

蛮力、分治与动态规划求解最大字段和问题的比较：

[QiYongchuan]

0/1背包问题

条件约束：

小于总重量

核心： 最优子结构性质分析 当第i个物体的重量超过背包总重量时，此时第i个装不进去，此时背包的最大价值就是第[i-1]个物体装入时的最大价值； 当第i个物体的重量不超过背包的总重量，可以装入背包时，此时可装可不装。

[QiYongchuan]

学习通试题及答案

[QiYongchuan]

考试前发疯belike：

五大算法，缺一不可！！！！！！

[QiYongchuan]

后续：考完了，但是资料还没有整理完的，暂时先将用到的pdf传到这里吧：

笔记.pdf 复习2+重点回顾.pdf 以及最后的模拟题： 考试题.pdf