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

《计算机算法导论部分知识点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法的概念：算法是解决问题的一种方法或者过程算法是若干指令的有穷序列包含以下5条性质：有0个或者多个输入至少一个输出有限性确定性可行性算法复杂性=算法所需的计算机资源算法复杂性是算法效率的度量算法的时间复杂性和算法的空间复杂性渐进上界O渐进下届渐进下界o非近下界w渐进近界分治法的设计思想：讲一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破之，分而治之分治法所能解决的问题一般具以下几个特征1：将问题的规模缩小到一定程度就可以容易地解决2：该问题具有最优子结构性质3：利用该问题分解出的子问题的解可以合并为该问题的解4：子问题之

2、间不包含公共的子问题分治法的步骤：1：分解：将原问题分解为若干规模较小，相互独立，与原问题形式相同的子问题2：解决：若子问题规模较小而容易被解决则直接解，否则递归的求解各个子问题3：合并：将各个子问题合并为原问题的解二分搜索技术：O（logn）快速排序：O(NLOGN)合并排序：O（LOGN^2）动态规划算法的基本要素：1：最优子结构性质2：重叠子问题性质动态规划的基本步骤：1：找出最优解性质，并刻画其结构特征2：递归地定义最优值3：以自底向上的方式计算最优值4：根据计算最优值时得到的信息，构造最优解动态规划算法的基本思想：将待解决的问题分解

3、成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解二分搜索算法是利用（动态规划算法）实现的算法贪心算法的基本思想：1：最优子结构性质2：贪心选择性质贪心选择算法的步骤：1：从问题的某个初始解出发2：采用循环结构，当可以向求解目标前进一步时，根据局部最优策略，得到一个部分解，缩小问题的范围或规模3：将所有部分解综合起来，得到问题的最终解贪心算法和动态规划算法的差别：相同点：具有最优子结构性质不同点：贪心算法不能解决0-1背包问题回溯法的基本思想：1：针对所给问题，定义该问题的解空间2：确定易于搜索的解空间结构3：以深度优先方式搜索解

4、空间结构，并在搜索过程中用剪枝函数避免无效搜索回溯法的搜索效率：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}