文档介绍：第第0 0讲:算法设计概论讲:算法设计概论时间复杂度时间复杂度空间复杂度空间复杂度调试方法与技巧调试方法与技巧时间复杂度时间复杂度??O O( (1 1)常数阶)常数阶??O O( ( log N log N )对数阶)对数阶??O O( (N N)线性阶)线性阶??O O( (N N^ ^2 2)平方阶)平方阶??O O( (N N^ ^3 3)立方阶)立方阶??…………………………………………空间复杂度空间复杂度??O O( (1 1)常数阶)常数阶??O O( ( log N log N )对数阶)对数阶??O O( (N N)线性阶)线性阶??O O( (N N^ ^2 2)平方阶)平方阶??O O( (N N^ ^3 3)立方阶)立方阶??…………………………………………调试方法与技巧调试方法与技巧?? Break Point Break Point ?? Watch Watch ?? Table Table ?? Data Data ?? Check Code Check Code 问题分析问题分析??分析题目的模型分析题目的模型??考虑要用的算法考虑要用的算法??分析算法的时空复杂度分析算法的时空复杂度??如果符合要求即可如果符合要求即可?? Coding Coding 第一讲:递归第一讲:递归什么是递归? 什么是递归? ??递归就是指一个函数直接或者间接地调用递归就是指一个函数直接或者间接地调用自身。自身。??问题的求解过程问题的求解过程??划分成相同性质的子问划分成相同性质的子问题的求解,而小问题的求解过程可以很容题的求解,而小问题的求解过程可以很容易的求出,这些子问题的解就构成里原问易的求出,这些子问题的解就构成里原问题的解。题的解。总体思想总体思想??待求解问题的解待求解问题的解??输入变量输入变量 x x的函数的函数 f f( (x x) ) ??通过寻找函数通过寻找函数 g g( ) ( ) ,使得,使得 f f( (x x) = ) = g g( (f f( (x x-1)) -1)) ??且已知且已知 f f(0) (0) 的值,就可以通过的值,就可以通过 f f(0) (0) 和和g g( ) ( ) 求出求出 f f( (x x) )值值推广推广??扩展到多个输入变量扩展到多个输入变量 x x, ,y y, ,z z等, 等, x x-1 -1也可以也可以推广到推广到 x x - - x x 1 1,只要递归朝着,只要递归朝着““出口出口””的的方向即可方向即可递归的三个要点递归的三个要点??递归式:如何划分子问题递归式:如何划分子问题??递归边界:递归的终止条件,也就是最小递归边界:递归的终止条件,也就是最小的子问题的子问题??界函数:问题规模变化的函数,保证递归界函数:问题规模变化的函数,保证递归向边界靠拢向边界靠拢