数据结构C语言版讲解课件.ppt

一个算法必须满足以下五个重要特性： 1．有穷性: 一个算法必须总是在执行有穷步之后结束， 且每一步都在有穷时间内完成。 2．确定性：算法的每一步必须是确切定义的， 不能产生二义性 3．可行性：算法是能够实现的.即算法描述的操作都是可以 通过已经实现的基本运算执行有限次来实现的。 4．有输入：一个算法有零个或多个输入 5．有输出：一个算法有零个或多个输出 二、算法设计的原则 设计算法时，通常应考虑达到以下目标： 1．正确性: 2. 可读性: 3．健壮性: 4．高效率与低存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。 标准：通常对于精心选择的典型、苛刻而带有刁难性的几组输入数据程序能够得出满足规格说明要求的结果。 算法应易于阅读和理解，以便于调试和修改。 算法应具有容错处理。当输入数据非法时，算法能做出适当的反应和进行特殊处理，而不是产年莫名其妙的输出结果。 三、算法效率的衡量方法和准则 通常有两种衡量算法效率的方法: 事后统计法： 事前分析估算法 1.事后统计：利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点： ?必须先运行依据算法编制的程序 ?所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣 2.事前分析估计： 一个高级语言程序在计算机上运行所消耗的时间取决于： ?依据的算法选用何种策略 ?问题的规模 ?程序语言 ?编译程序产生机器代码质量 ?机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———使用绝对时间单位衡量算法效率不合适 算法 = 控制结构 + 基本操作 算法的执行时间 = 基本操作(i)的执行次数×基本操作(i)的执行时间 算法的执行时间 与 基本操作执行次数之和 成正比 如何估算算法的时间复杂度？ 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。 算法中基本操作（循环）重复执行的次数是问题规模n的某个函数f(n),它是一个算法运行时间的相对量度,算法的时间量度记作： T(n)=O(f(n)) 时间复杂度的渐进表示法 它表示随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，T(n) 称作算法的(渐近)时间复杂度。 例1： {++x;s=0;} 1 O(1) for(i=1;i=n;++i) {++x;s+=x;} n O(n) for(j=1;j=n;++j) for(k=1;k=n;++k) {++x;s+=x;} n*n O(n2) 例2： 例3： 频度 时间复杂度 程序 时间复杂度的计算： 例4： void mult(int a[], int b[], int c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; ++i) for (j=1; j=n; ++j) { c[i,j] = 0; for (k=1; k=n; ++k) c[i,j] += a[i,k]*b[k,j];//语句的频度: 重复执行的次数：n3; } //for } //mult 基本操作: 乘法操作 时间复杂度: O(n3) T( n ) = O ( n 3) 即：矩阵乘法的运算量和问题的规模n的立方是同一个量级 x = 0; y = 0; for ( int k = 0; k n; k ++ ) x ++; for ( int i = 0; i n; i++ ) for ( int j = 0; j n; j++ ) y ++; T1(n) = O(1) T2(n) = O(n) T3(n) = O(n2) T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2) 例5： void exam ( float x[ ][ ], int m, int n ) { float sum [ ]; for ( int i = 0; i m; i++ ) { //x中各行数据累加 sum[i] = 0.0; for ( int j