2021年算法引论及简单算法.ppt

2021年算法引论及简单算法730708126*
注 意
算法是程序设计的灵魂
算法引论及简单算法730708126
*
*
与数据结构的区别：
考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。
考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。
与其他课程的关系
高级程序设计语言（C语言，等）
数据结构
算法设计与分析
系统的设计与实现
算法引论及简单算法730708126
*
*
主要内容
目标：了解算法分析的基本含义。掌握查找算法、排序算法、递推算法等算法理念。
提纲
算法分析
查找算法
排序算法
递推算法
算法引论及简单算法730708126
*
*
算法分析
前面的课程内容以C语言语法为主
本补充章介绍一些基本算法
大家在编写程序的时候，“八仙过海，各显神通”，解决同一个问题，可以使用各种方法。
算法之间存在着“优劣”之分
算法引论及简单算法730708126
*
*
算法分析
1、算法分析的目的

通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。
算法引论及简单算法730708126
*
*
算法分析
2、算法分析的含义
算法分析是一种分析技术，它以独立于具体的硬件平台、编译器和编程语言的方式，来描述算法的执行行为，即它关心的是算法，而不是程序。
算法分析是一种测量算法的性能的方法，它不关心精确的细节，如在算法的某次运行中总共执行了多少条机器指令，而是想要一个大致的估计，即随着输入数据规模的增大，算法所需工作量以何种速度递增。（关心变化趋势）
算法引论及简单算法730708126
*
*
算法分析
3、算法复杂性
时间复杂性和空间复杂性
算法引论及简单算法730708126
*
*
算法分析
，一旦达到这个上限，程序将被强制结束。
。
为什么要考虑时间复杂性？
算法引论及简单算法730708126
*
*
，需指明分配给该程序的内存大小。
。
，从中择取。
。
考虑程序的空间复杂性的理由：
算法分析
算法引论及简单算法730708126
*
*
4. 如何进行算法分析？
事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο）——与计算机软硬件没有直接关系。
事后测试：将算法编制成程序后放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。
算法分析
算法引论及简单算法730708126
*