算法引论及简单算法.ppt

算法引论及简单算法730708126*注意算法是程序设计的灵魂*与数据结构的区别:考虑问题的角度:数据结构关心不同的数据结构在解题中的作用和效率;算法关心不同设计技术的适用性和效率。考虑问题的高度:数据结构关心的是解具体问题,算法不仅如此,它提供一种解决问题的通用方法。与其他课程的关系高级程序设计语言(C语言,等)数据结构算法设计与分析系统的设计与实现*主要内容目标:了解算法分析的基本含义。掌握查找算法、排序算法、递推算法等算法理念。*,“八仙过海,各显神通”,解决同一个问题,可以使用各种方法。算法之间存在着“优劣”之分*、算法分析的目的通过对算法分析,在把算法变成程序实际运行前,就知道为完成一项任务所设计的算法的好坏,从而运行好算法,改进差算法,避免无益的人力和物力浪费。*、算法分析的含义算法分析是一种分析技术,它以独立于具体的硬件平台、编译器和编程语言的方式,来描述算法的执行行为,即它关心的是算法,而不是程序。算法分析是一种测量算法的性能的方法,它不关心精确的细节,如在算法的某次运行中总共执行了多少条机器指令,而是想要一个大致的估计,即随着输入数据规模的增大,算法所需工作量以何种速度递增。(关心变化趋势)*、算法复杂性时间复杂性和空间复杂性*,一旦达到这个上限,程序将被强制结束。。为什么要考虑时间复杂性?*,需指明分配给该程序的内存大小。。,从中择取。。考虑程序的空间复杂性的理由:*?事前分析:就算法本身,通过对其执行性能的理论分析,得出关于算法特性——时间和空间的一个特征函数(Ο)——与计算机软硬件没有直接关系。事后测试:将算法编制成程序后放到计算机上运行,收集其执行时间和空间占用等统计资料,进行分析判断——直接与物理实现有关。