算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。 算法+数据结构=程序,求解一个给定的可计算或可解的问题,不同的人可以编写出不同的程序,来解决同一个问题,这里存在两个问题:一是与计算方法密切相关的算法问题;二是程序设计的技术问题。算法和程序之间存在密切的关系。分析算法可以预测这一算法适合在什么样的环境中有效地运行,对解决同一问题的不同算法的有效性作出比较。 分析对象—(时间、空间)算法复杂度 但是,上述说法比较含糊…... 算法复杂度=程序测量结果? 这种程序测量方法缺陷明显:(1)它需要先将算法实现为程序,并在具体机器上运行获得,是一种事后行为;(2)会受到实现和运行程序的具体环境影响; 如何进行算法分析:分析手段----程序步计数 程序步:是指在语法上或语义上有意义的语句,其执行1次的时间与问题规模n无关; 所有程序步的单位执行时间相同 ,通过在程序中统计程序步总的执行次数来了解其运行时间。 程序步计数法应用--顺序查找(利用计数器count进行统计) 程序步计数法改进 程序步计数法操作步骤–从程序代码中抽出基本语句——程序步 –筛选出主要程序步 –统计其执行次数 –获得T(n)——以n为自变量的函数 人们更关注: n增大时,T(n)的增长趋势如何? “算法设计与分析”有用 算法是计算机科学的核心主题之一,其重要性不言而喻。有一个好的算法设计与分析功底是从事计算机相关各种工作的坚实基础。从就业来看,算法基础是许多名企面试必考的内容;从科学研究来看,算法设计与分析是计算机科学诸多领域研究中必须的技能。 “算法设计与分析”有趣 这是一门有趣的课程,算法给了我们一个看待世界和看待生活的新方式,从中学到的不仅是让计算机做事情的方式,还有“递归”、“分治”“优化”、“剪枝”等等一系列可能改变生活的思维方法。 “算法设计与分析”需要努力学习 和很多知识性的课程不同,算法设计与分析是一门重视能力的课程,如同九阴真经,是一门既修炼“内功”也修炼内功的学科。因此学习算法设计与分析既需要像数学课一样的证明、又需要像程序设计语言一样的写码,因而需要格外的努力才可以学得好。 |
|