算法及基础知识

《算法及基础知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析张阳信息工程学院教师简介张阳信息工程学院109zhangyang@nwsuaf.edu.cn教学资源：作业管理系统-张阳课程简介课时：理论课36+实验课12=48成绩：平时30+考试70=100平时：作业+实验+实验考核+考勤教材：《算法设计与分析》王秋芬、吕聪颖等编著清华大学出版社2011年8月参考算法设计与分析王晓东第二版清华大学出版社（JAVA）算法设计与分析王晓东第二版清华大学出版社（C/C++）课程简介学习算法的理由：一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。——Ge

2、orgeForsythe《计算机科学家到来以前我们做什么》1968算法是计算机科学的基石。没有算法，计算机程序将不复存在，另外学习算法可以提高人们的分析能力。算法可以看作是解决问题的一类特殊方法——它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。课程简介算法的魅力：思考程序=算法+数据结构算法让我们上一个更高的台阶要求:思考+预习/复习+实践上课：不旷课、不迟到课程简介第1章算法及基础知识第2章贪心法第3章分治法第4章动态规划第5章搜

3、索法第6章随机化算法第9章NP完全理论第1章算法概述学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握用C++/JAVA语言描述算法的方法。第1章算法概述算法：对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。算法的特性输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性描述方式自然语言、图形、程序设计语言、伪代码本书采用了面向对象程序设计语言C++思考：算法与程序的区别？第1章算法概述程序(Program)程序

4、是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。操作系统：是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。最大共约数求：非负整数M和N的最大公约数，记为：Gcd(m,n)方法一：欧几里得算法Gcd(m,n)=Gcd(n,mmodn)Gcd(60,24)=Gcd(24,12)=Gcd(12,0)=12方法二：连续整数检测算法（1）将min(m,n)的值赋给t。（2）m除以t，如果余数为0，进入第3步，

5、否则，进入第4步。（3）n除以t，如果余数为0，返回t值，结束，否则，进入第4步。（4）t=t-1，返回第2步。方法三：中学里计算Gcd(m,n)的过程（用数学定义的方法）（1）找到m的所有质因数。（2）找到n的所有质因数。（3）找到（1），（2）中的公因数。（4）求公因数的积，该乘积为m、n的最大公约数。问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法算法设计1．理解问题2．了解计算机设备的性能3．在精确解法和近似解法间做选择4．确定适当的

6、数据结构5．算法设计技术6．详细表述算法的方法7．证明算法的正确性8．分析算法9．为算法写代码问题N后问题01背包问题布线问题n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1234567812345678QQQQQQQQ01背包问题布线问题起点XXXXXXXXXXXXXXXXXXXX终点XXXXX算法复杂性=算法运行时所需要的计算机资源的量时

7、间复杂性、空间复杂性影响时间复杂性的因素问题规模n、输入序列I、算法本身A影响空间复杂性的因素算法本身、输入输出数据、辅助变量算法复杂性的权衡时间复杂度和空间复杂度相互影响时间换空间或空间换时间1.3算法分析例：查找操作，三种情况下的复杂性最好情况Tmin（N)1次最坏情况Tmax（N)N次平均情况Tavg（N)(N+1)/21.3算法分析算法渐近复杂性态设算法的运行时间为T(n)，如果存在T*(n)，使得就称T*(n)为算法的渐进性态或渐进时间复杂性。1.3算法分析1.3算法分析假设算法A的运行时间表达式为T1

8、(n)T1(n)=30n4+20n3+40n2+46n+100假设算法B的运行时间表达式为T2(n)T2(n)=1000n3+50n2+78n+10算法A的运行时间可记为：T*1(n)≈n4算法B的运行时间可记为：T*2(n)≈n3渐近意义下的记号：O、Ω、θ、o设f(N)和g(N)是定义在正数集上的正函数。O的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(