数据结构实用教程C语言版 董凤服及算法 第1章 概论.ppt

4．算法的描述 为了表示一个算法，可以用多种不同的方法，常用的有自然语言、传统流程图、结构化流程图、N-S流程图等表示。本书采用C的描述语言实现对各种数据结构及算法的操作描述，算法是以函数形式描述，描述如下： 类型标识符 函数名(形式参数表) /*算法说明*/ { 语句序列 } 返回到本节目录 1.2.1 算法的概念 * 1.2.2 算法分析 在算法满足正确性的前提下，如何评价不同算法的优劣呢？通常主要考虑算法的时间复杂度和空间复杂度这两方面。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度作为重点分析。 1. 时间复杂度（Time Complexity） 一个算法所需的运算时间通常与所解决问题的规模大小有关。问题规模是一个和输入有关的量，用n 表示问题规模的量，把算法运行所需的时间T表示为n的函数，记为T(n)。不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。一个算法所需的执行时间就是该算法中所有语句执行次数之和。当n逐渐增大时T(n)的极限情况，一般简称为时间复杂度。 返回到本节目录 * 当讨论一个程序的运行时间时，注重的不是T(n)的具体值，而是它的增长率。T(n)的增长率与算法中数据的输入规模紧密相关，而数据输入规模往往用算法中的某个变量的函数来表示，通常是f(n)。随着数据输入规模的增大，f(n)的增长率与T(n)的增长率相近，因此T(n)同f(n)在数量级上是一致的。记作： T(n)=O(f(n)) 其中，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。 返回到本节目录 1.2.2 算法分析 * 返回到本节目录 1.2.2 算法分析 * 【例1.6】分析以下算法的时间复杂度。 x=0;y=0; for(k=1;k=n;k++) x++; （1）执行n次 for(i=1;i=n;i++) for(j=1;j=n;j++) y++; （2）执行n2次 解：T(n)= n+n2 T(n)=O(n2) 上述算法中的基本运算是语句（2），其执行频率为n2。则T(n)=n2=O(n2) 返回到本节目录 1.2.2 算法分析 * 【例1.7】分析以下算法的时间复杂度。 i=1; while(i=n) i=2*i; (1) 执行f(n)次 解：设语句（1）执行次数是f(n)，则2f(n)≤n 得到T(n)=O(log2n) 返回到本节目录 1.2.2 算法分析 * 【例1.8】求两个矩阵相乘的函数的时间复杂度。 void mult(int a[], int b[], int c[]) {/*以二维数组存储矩阵元素，c为a和b的乘积*/ for(i=1;i=n;++i) (1) 执行n次 for(j=1;j=n;++j) (2) 执行n2次 { c[i,j]=0; for(k=1;k=n;++k) (3) 执行n3次 c[i,j]+=a[i,k]*b[k,j]; } } 解：嵌套循环为每层循环次数的乘积，因为是该函数为三重循环，所以时间复杂度为O(n3)。 返回到本节目录 1.2.2 算法分析 * 2. 空间复杂度（Space Complexity） 一个算法的空间复杂度是指程序运行开始到结束所需要的存储空间。包括算法本身所占用的存储空间、输入/输出数据占用的存储空间以及算法在运行过程中的工作单元和实现算法所需辅助空间。类似于算法的时间复杂度，算法所需存储空间的量度记作： S(n)=O(f(n)) 表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。 返回到本节目录 1.2.2 算法分析 * 1.2.3 相关C语言知识回顾 1．数据类型 数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序设计语言中，用以描述操作对象的特性。高级语言中的数据类型可分为两类：一类是原子类型，如C语言中的基本类型（整型、实型、字符型等）指针和空类型等不可再分的值；另一类是结构类型，如数组、结构体等通过若干成分（可以是原子类型或结构类型）构造而成的。 返回到本节目录 * 1.2.3 相关C语言知识回顾 （1）数组类型 数组中的每一个元素都属于同一个数据类型。数组有一维数组和多维数组，数组名标识一个数组，下标指示一个数组元素在该数组中的顺序位置，下标从0～n-1（n为数据元素个数）。例如，int a[10];定义了包含10个整