文档介绍：蒋瀚 ******@sdu.
山东大学计算机科学与技术学院
2009-2010年度秋季学期动漫08
数据结构算法与应用--C++ 语言描述
什么是数据结构?
在计算机科学中,数据结构(data structure)是计算机中存储、组织数据的方式。
什么是算法?
算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据,能够得出所要求或期望的终止状态或输出数据。
--维基百科
C++ 简介
C++是一种使用非常广泛的计算机程序设计语言。
贝尔实验室的比雅尼·斯特劳斯特鲁普博士在20世纪80年代发明并实现了C++。
1998年国际标准组织(ISO)颁布了C++程序设计语言的国际标准ISO/IEC 14882-1998。
C++语言发展大概可以分为三个阶段
80年代到1995年:这一阶段C++语言基本上是传统类型上的面向对象语言。
1995年到2000年,泛型程序设计在C++中占据了越来越多的比重。
从2000年至今,产生式编程和模板元编程。
C++已经成为当今主流程序设计语言中最复杂的一员
--维基百科
第2章程序性能
运行一个程序所需要的内存大小和时间
分析的方法
实验的方法
运行完一个程序所需要的内存大小
运行完该程序所需要的时间
存储经过编译之后的程序指令所需的空间
存储所有常量和所有变量值所需的空间
保存函数调用返回时恢复运行所需要的信息
首先选择一种或几种关键操作,然后确定关键操作分别执行了多少次
要统计程序/函数中所有部分的时间开销
对一个程序的空间复杂性感兴趣的主要原因如下:
如果程序将要运行在一个多用户计算机系统中,可能需要指明分配给该程序的内存大小。
对任何一个计算机系统,想提前知道是否有足够可用的内存来运行该程序。
一个问题可能有若干个内存需求各不相同的解决方案。
可以利用空间复杂性来估算一个程序所能解决的问题的最大规模。
对一个程序的时间复杂性感兴趣的主要原因如下:
有些计算机需要用户提供程序运行时间的上限,一旦达到这个上限,程序将被强制结束。
正在开发的程序可能需要提供一个满意的实时响应。
如果有多种可选的方案来解决一个问题,那么具体决定采用哪一个主要基于这些方案之间的性能差异。
渐进符号
大写O 符号给出了函数f的一个上限。
f(n)=O(g(n)):当且仅当存在正的常数c和n0,使得对于所有的n≥n0 , 有f(n)≤cg(n)。
Ω符号与大O 符号类似,它用来估算函数f 的下限值。
f(n)= Ω(g(n)):当且仅当存在正的常数c 和n0,使得对于所有的n≥n0,有f(n) ≥cg(n)。
Θ符号适用于同一个函数g 既可以作为f 的上限也可以作为f 的下限的情形。
f(n)=Θ(g(n)):当且仅当存在正常数c1 , c2 和某个n0,使得对于所有的n≥n0 ,有c1g(n)≤f(n)≤c2g(n)。
小写o符号
f(n)=o(g(n) ):当且仅当f(n)=O(g(n))且f(n)≠Ω(g(n))。
例一递归问题
递归函数是一个自己调用自己的函数。
递归函数包括两种
直接递归
间接递归
例一递归问题
程序1-7 计算n!的递归函数
int Factorial (int n)
{
//递归计算n!
if (n<=1) return 1;
else return n * Factorial(n- 1 ) ;
}
P36 练习7 计算n!的非递归程序
int factorial (int n)
{
//非递归计算n!
if (n <= 1) return 1;
int fact = 2;
for (int i = 3; i <= n; i++)
fact *= i;
return fact;
}