考前知识点整理课程介绍算法分析基础算法的定义算法正确性算法的性质程序的定义程序与算法的区别算法设计和分析的步骤复杂度分析算法的时间复杂性算法渐近复杂性渐近分析的记号渐近上界记号渐近下界记号非紧上界记号非紧下界记号紧渐近界记号意义 算法分析中常见的复杂性函数算法分析方法算法分析的基本法则递归基本概念递归优缺点递归树方法主方法主定理主定理解析主定理举例分治法总体思想适用条件归并排序算法的复杂度分析归并算法的改进快速排序动态规划算法总体思想动态规划基本步骤动态规划算法的基本要素备忘录方法0-1背包实例最长公共子序列矩阵连乘分析最优解的结构建立递归关系递归的复杂性计算最优值DP求解的复杂度分析构造最优解贪心算法贪心算法与分治法和动态规划算法的关系贪心算法的基本思想贪心算法的基本要素两个背包问题前缀码回溯算法生成问题状态的方法回溯法的基本思想n皇后问题4皇后问题的解空间使用剪枝函数的4皇后问题的状态空间树n皇后问题及回溯算法N-QUEEN算法代码分析分支限界法分支限界法与回溯法的区别分支限界法基本思想常见的两种分支限界法两种分支限界法的异同先进先出状态空间树优先队列状态空间树组合优化问题代价函数界分支限界Sample Testselect questionfill blankshort question什么是算法？算法的特征有哪些？主定理简述分治法的适用条件（特征）设计动态规划算法的基本步骤动态规划算法的基本思想简述分支限界法与回溯法的不同简述递归的定义及优缺点简述回溯法的一般执行步骤回溯法的基本原理简述分治法和动态规划算法的相同点和不同点简述常见的两种分支限界法贪心算法与分治法和动态规划算法的异同贪心算法的基本元素分支限界法与回溯法的区别分支界限法的基本思想分支限界法设计算法的步骤动态规划与备忘录算法的比较常用的剪枝函数矩阵连乘问题什么是递归算法？递归算法的特点？两个要素？适合用分治算法求解的问题具有的基本特征？动态规划算法解题步骤？渐进表示的定义考虑算法的好坏的因素最优子结构递归循环与迭代算法分析的目的典型的解空间树：子集树和排列树分支限界法的搜索策略二叉查找法算法基本思想归并排序 calculate questionalgorithm analysisMergeSortLCSQuickSortBubbleSortN皇后问题最大团问题 design questionPDF版获取方式1方式2方式3后序 我们学校开设的这门课，过于理论，实践太少，考试不会太难，一起学习，一起 不挂科！ 但是算法平时一定要练哦！加油！ 内容摘自老师PPT及复习资料，感谢！
感兴趣的话可以参考 算法竞赛、小白学DP(动态规划) 学习相关代码的具体实现(Java版)
课程介绍 
算法分析基础 算法的定义 算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列。
算法正确性 对每一个输入实例算法都能终止，并给出正确输出。
算法的性质 (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 （可行性）
程序的定义 程序是算法用某种程序设计语言的具体实现。
程序与算法的区别 程序可以不满足算法的性质(4)（有限性）。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，当子程序得到输出结果后便终止。
这个好像要考(*￣︶￣)
算法设计和分析的步骤 （1）问题的陈述。 （2）模型的选择。 （3）算法的设计。 （4）算法的程序实现。 （5）算法分析。
复杂度分析 算法复杂性 = 算法所需要的计算机资源 1、考虑算法的好坏主要有以下几点： （1）执行算法所耗费的时间。 （2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间。 （3）算法应易于理解，易于编码，易于调试等。
2、影响程序运行时间的主要因素 ： （1）程序的输入。 （2）由编译系统所产生的代码程序的质量。 （3）执行程序的计算机机器指令的性能与速度。 （4）程序所依据的算法的时间复杂度。
3、算法的复杂性测度主要有两个方面： (1) 时间复杂度 T(n) (2) 空间复杂度 S(n) 其中n是问题的规模（输入大小）。
算法的复杂性取决于：
(1)求解问题的规模N； (2)具体的输入数据I； (3)算法本身的设计
可操作性最好且最有实际价值的是最坏情况下的时间复杂性。
算法的时间复杂性 
算法渐近复杂性 
渐近分析的记号 渐近上界记号 
渐近下界记号 
非紧上界记号 
非紧下界记号 
紧渐近界记号 
意义 
算法分析中常见的复杂性函数 
算法分析方法 
算法分析的基本法则 
递归 基本概念 递归的概念:
直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。
说明:
1、递归程序必须有终止条件。否则就总是自我调用，永不终止。 2、尽管递归程序在执行时间上往往比非递归程序要付出