计算机算法导论部分知识点.doc

算法的概念：
算法是解决问题的一种方法或者过程
算法是若干指令的有穷序列
包含以下5条性质：
有0个或者多个输入
至少一个输出
有限性 确定性 可行性
算法复杂性=算法所需的计算机资源
算法复杂性是算法效率的度量
算法的时间复杂性和算法的空间复杂性
渐进上界O 渐进下届 渐进下界o
非近下界w
渐进近界

分治法的设计思想：讲一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破之，分而治之

分治法所能解决的问题一般具以下几个特征
1：将问题的规模缩小到一定程度就可以容易地解决
2：该问题具有最优子结构性质
3：利用该问题分解出的子问题的解可以合并为该问题的解
4：子问题之间不包含公共的子问题

分治法的步骤：
1：分解：将原问题分解为若干规模较小，相互独立，与原问题形式相同的子问题
2：解决：若子问题规模较小而容易被解决则直接解，否则递归的求解各个子问题
3：合并：将各个子问题合并为原问题的解

二分搜索技术 ：O（logn）
快速排序：O(NLOGN)
合并排序：O（LOGN^2）

动态规划算法的基本要素：
1：最优子结构性质
2：重叠子问题性质

动态规划的基本步骤：
1：找出最优解性质，并刻画其结构特征
2：递归地定义最优值
3：以自底向上的方式计算最优值
4：根据计算最优值时得到的信息，构造最优解

动态规划算法的基本思想：
将待解决的问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解

二分搜索算法是利用（动态规划算法）实现的算法

贪心算法的基本思想：
1：最优子结构性质
2：贪心选择性质

贪心选择算法的步骤：
1：从问题的某个初始解出发
2：采用循环结构，当可以向求解目标前进一步时，根据局部最优策略，得到一个部分解，缩小问题的范围或规模
3：将所有部分解综合起来，得到问题的最终解

贪心算法和动态规划算法的差别：
相同点：具有最优子结构性质
不同点：贪心算法不能解决 0-1背包问题

回溯法的基本思想：
1：针对所给问题，定义该问题的解空间
2：确定易于搜索的解空间结构
3：以深度优先方式搜索解空间结构，并在搜索过程中用剪枝函数避免无效搜索

回溯法的搜索效率：
1：产生x【k】的时间
2：满足显约数的x【k】值的个数
3：计算约束函数constaint的时间】
4：计算上界函数bound的时间
5：满足约束函数和上界函数的所有x【k】的个数
最优子结构性质：某问题的最优解包含着其子问题的最优解。

分支限界法的两种形式：
队列式分支限界法
优先队列式分支限界法

分支限界法的基本思想：
分支限界法以广度优先或最小耗费优先的方式搜索问题的解空间树

{1}
{1,2}
{1,2,4}
{1,2,4,3}
{1,2,4,3,5}