1.2算法和复杂度.ppt

1、1.3-1.4算法和算法分析、算法和复杂度、2/24、算法：是特定问题解决步骤的描述、指令的有限系列、每条指令代表一个或多个操作。1.3.1算法的概念、算法和复杂度、3.其中一个算法通常具有五个重要特性：穷人有限步骤结束，仅有的确定性的可执行路径(无模糊性)，可行性实现在基本运算中，输入0或多个输入并输出一个或多个输出。 24数据结构由算法实现操作，算法根据数据结构设置纠正计程仪程序、算法和复杂度、4/24、算法设置纠正要求：准确反映(测试合格)需求，可读性有助于理解、调试和维护的一般算法设置纠正方法， 列举了穷法在问题空间中的所有求解对象，并逐一进行分析处理，验证结果是否满足规定的条件。 回

2、溯算法按某一顺序逐个列举问题的候补解进行验证，寻找满足预定条件的解。 在已知当前的候补解不可能是解的情况下，返回到上一步骤再次选择下一候补解(背轨)。 (例如八皇后、迷宫、深度优先搜索)、算法和复杂度、6/24、如果遇到分治法难以直接解决的大问题，把它分割成几个规模的小的子问题，分割每个子问题的解，将其合并，得到问题整体的解(例如高速排序等)贪婪算法的基本思想， 从问题的初始状态，基于某个贪婪标准，通过几次贪婪选择得到局部最佳解，并将最终全局最佳解建构局部最佳解。 算法和复杂度、7/24、1.4算法分析、算法效率的测定方法1事后统计利用订正机内记机能。 缺点：根据算法编制的计程仪程序必须先执行

3、的时间总量取决于硬件、软件等环境要素，算法本身的优劣、算法和复杂性、8/24、 1.4隐藏算法分析算法效率的测定方法2高级语言计程仪程序在计算机上运行的时间，选择什么策略问题的规模程序语言编译程序生成机械查询密码质量机器运行指令速度时间复杂度和空间复杂度、算法和复杂度、9/24、算法时间校准预测， 从算法中选择用于研究问题的基本操作的源操作并重复执行该基本操作的时间校正预测，基本操作的重复执行次数分别为1、n、n-2、算法和复杂度、10/24、算法的复杂度、问题的规模(n ) :或大小。 例如，矩阵的阶数、图的节点数、以及所分类的序列的正整数时间复杂度：算法所需的时间和问题规模的函数。 记为T

4、(n )。 n时的时间复杂度被称为渐进时间复杂度。 空间复杂度：算法所需空间和问题规模的函数。 记为S(n )。 n时的时间复杂度被称为渐进空间复杂度。 给出算法和复杂度，11/24，两个正值函数f和g，定义1 :如果存在正值c和n，并且对所有的nN存在f(n)cg(n )，那么定义为f(n)=o ()。 从上述定义可知，对于一盏茶大的n，或大于某自然数n，如果存在正数c，f不大于cg，则f是g大的o符号。其中，g(n)=n2，c和n的可选择值如表所示： O(nn )常数对数多项式指数、复杂度示例、算法和复杂度、14/24、复杂度示例、算法的坏的算法不一定有实际意义。 举例说明。 设时间复杂性函数的时间单位为us。 函数n=20 n=50 n=100 n=5001000 n.02 s.05 s.5 s 1000 nlogn.09 s.3 s.6 s4.5s 100 n2. 04 s 2n/3 .0001s 0.1s 2.7小时5 108世纪