L05-L06算法分析与数据结构.ppt

网络游戏算法设计,第2章 算法分析与数据结构,第2章 算法分析与数据结构,算法描述 数据抽象 算法复杂度的计算,了解算法描述 了解数据抽象 掌握算法复杂度的计算,第2章 算法分析与数据结构,算法复杂度的计算,算法复杂度的计算,第2章 算法分析与数据结构,使用计算机解决实际问题的过程，就是分析问题涉及的数据、合理组织数据以及规划解决问题的算法的过程。,在计算机科学的发展过程中，分析、组织数据和规划算法被单独成一个学科，这就是数据结构。,数据结构在计算机科学技术中，尤其是在网络游戏程序设计中起到了举足轻重的作用。数据结构是网络游戏开发的核心知识之一，是许多后续内容的重要基础。,第2章 算法分析与数据结构,2.1 算法描述,算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。,算法的描述方法可以归纳为以下4种： 1）自然语言； 2）图形，如NS图、流程图，图的描述与算法语言的描述对应； 3）算法语言，即计算机语言、程序设计语言、伪代码； 4）形式语言，用数学的方法，可以避免自然语言的二义性。,第2章 算法分析与数据结构,2.2 数据抽象,数据抽象类型给出了一种用户定义的数据类型，其运算符指明了用户如何操作数据，数据抽象类型与具体应用无关，这可使程序员把注意力集中在数据及其操作的理想模型上。,class Cirle public: Cirle(float r) m_Radii = r; float Area(); / 计算圆面积 float Cirumference(); / 计算圆周长 private: float m_Radii; ;,第2章 算法分析与数据结构,2.3 算法复杂度的计算,2.3.1 空间复杂度,程序所需要的空间主要由指令空间、数据空间、环境栈空间构成。, 指令空间,指令空间是指用来存储经过编译之后的程序指令所需的空间。,程序所需要的指令空间的数量取决于如下因素： 1）把程序编译成机器代码的编译器； 2）编译时实际采用的编译器选项； 3）目标计算机。,第2章 算法分析与数据结构,2.3 算法复杂度的计算, 数据空间,数据空间是指用来存储所有常量和所有变量值所需的空间。数据空间包括： 1）存储常量和简单变量所需要的空间,2）存储复合变量所需要的空间。这一类空间包括数据结构所需的空间及动态分配的空间。,int i = 4, j = 5;,int iArray256;,第2章 算法分析与数据结构,2.3 算法复杂度的计算,对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器，以及变量与常量的数目。,对于一个结构变量，可以把它的每个成员所占用的空间累加起来即可得到该变量所需要的内存。,double a100; int mazerowscols;,数组a 需要的空间为100个double类型元素所占用的空间，若每个元素占用8个字节，则分配给该数组的空间总量为800字节。数组maze有rows*cols个int类型的元素，它所占用的总空间为4*rows*cols字节。,第2章 算法分析与数据结构,2.3 算法复杂度的计算, 环境栈空间,环境栈用来保存函数调用返回时恢复运行所需要的信息。,每当一个函数被调用时，下面的数据将被保存在环境栈中： 1）返回地址； 2）函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言）； 3）所有引用参数及常量引用参数的定义。,第2章 算法分析与数据结构,2.3 算法复杂度的计算,2.3.2 时间复杂度,影响一个程序空间复杂性的因素也能影响程序的时间复杂性。,一个程序P所占用的时间T (P)=编译时间+运行时间。编译时间与实例的特征无关。 可以假定一个编译过的程序可以运行若干次而不需要重新编译。因此将主要关注程序的运行时间。运行时间通常用“t p(实例特征)”来表示。,第2章 算法分析与数据结构,2.3 算法复杂度的计算,计算t p 的公式,t p (n) = ca ADD (n) + cs SUB (n) + cm MUL (n) + cd DIV (n) + ,n代表实例的特征，其中c a、c s、 cm 和cd分别表示一个加、减、乘和除操作所需要的时间，函数ADD、SUB、MUL和DIV分别表示代码P中所使用的加、减、乘和除操作的次数。,有两个更可行的方法可用来估算运行时间： 1）找出一个或多个关键操作，确定这些关键操作所需要的执行时间； 2）确定程序总的执行步数。,第2章 算法分析与数据结构,2.3 算法复杂度的计算, 操作计数,估算一个程序或函数的时间复杂性的一种方式就是首先选择一种或多种操作（如加、乘和比较等），然后确定这种或这些操作分别执行了多少次。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。,int Max(int a, int n) int pos = 0; for (int i = 1; i n; i+) if (apos ai) pos = i; return pos; ,第2章 算法分析与数据结构,2.3 算法复杂度的计算, 执行步数,在统计执行步数的方法中，要统计程序（函数）中所有部分的时间开销。与操作计数一样，执行步数也是实例特征的函数。,尽管任意一个特定的程序可能会有若干个特征，但可以把执行步数看成是其中一部分特征的函数。通常选择一些感兴趣的特征,定义一个操作步。操作步是独立于所选特征的任意计算单位.,可以通过创建一个全局变量count（其初值为0）来确定一个程序或函数为完成其预定任务所需要的执行步数。,小结,第2章 算法分析与数据结构,本章介绍了算法描述的基本方法。算法是解题的步骤，可以把算法定义成解决某类问题的任意一种有序方法。算法可以用自然语言、图形、算法语言、形式语言对算法进行描述。算法的性能可以用空间复杂度和时间复杂度来进行描述。程序所需要的空间主要由指令空间、数据空间、环境栈空间构成。通过对这3个空间的分析就可以得出算法的空间性能。时间复杂度用来描述算法在时间上的性能，可以通过“操作计数”、“执行步骤”对时间复杂度进行分析。,小测验,第2章 算法分析与数据结构,选择题（单选题）,程序所需要空间指的是（ ）。 A指令空间、数据空间、环境栈空间 B指令空间、局部空间 C全局空间、局部空间、栈空间 D指令空间、命名空间 计算机算法指的是（ ）。 A计算方法 B排序方法 C解决某类问题的任意一种有序方法 D调度算法,小测验答案,第2章 算法分析与数据结构,选择题（单选题）,程序所需要空间指的是（ A ）。 A指令空间、数据空间、环境栈空间 B指