(4) 效率指的是算法执行的 时间;存储量需求指算法执行过程中所需要的 最大存储空间。一般,这两者与问题的规模有 关 对一个算法要作出全面的分析可分成两用人 才个阶段进行,即 和 求出该算法的一个时间界限函数 收集此算法的执行时间和实际占用 空间的统计资料。 定义:如果存在两个正常数c和n0,对于所有的 n三n0,有|fn)|sclg(n) 。则记作fn)=O(g(n)
⚫ (4)效率与存储量需求 效率指的是算法执行的 时间；存储量需求指算法执行过程中所需要的 最大存储空间。一般，这两者与问题的规模有 关。 ⚫ 1.4.3 算法效率的度量 ⚫ 对一个算法要作出全面的分析可分成两用人 才个阶段进行，即事先分析和事后测试 ⚫ 事先分析 求出该算法的一个时间界限函数 ⚫ 事后测试 收集此算法的执行时间和实际占用 空间的统计资料。 ⚫ 定义：如果存在两个正常数c和n0，对于所有的 n≧n0，有︱f(n) ︳≦c｜g(n) ︳ ⚫ 则记作 f(n)=O(g(n))
般情况下,算法中基本操作重复执行的 次数是问题规模n的某个函数,算法的时 间量度记作 T(n=o(f(n)) 称作算法的渐近时间复杂度 例1、for(l=1,I<=n:++1) for(=1j<=n;++j) c=0: for(k-1; k<=n; ++k) c团订]+=a[k]*bk]
一般情况下，算法中基本操作重复执行的 次数是问题规模n的某个函数，算法的时 间量度记作 T(n)=O(f(n)) 称作算法的渐近时间复杂度。 例１、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]; }
。由于是一个三重循环,每个循环从1到n,则总 次数为:n×n×n=n3 时间复杂度为T(n)=O(n3) 是指该语句重复执行的次数 。例2{++x;s=0;} 将x自增看成是基本操作,则语句频度为1, 即时间复杂度为O(1) 如果将s=0也看成是基本操作,则语句频度为 2,其时间复杂度仍为O(1),即常量阶 例3、for(=1,<=n;++D {++xs+=x2} 语句频度为:2n其时间复杂度为:O(n) 即时间九舞阶
⚫ 由于是一个三重循环，每个循环从1到n，则总 次数为: n×n×n=n3 ⚫ 时间复杂度为T(n)=O(n3) ⚫ 频度：是指该语句重复执行的次数 ⚫ 例２ {++x;s=0;} ⚫ 将x自增看成是基本操作，则语句频度为１， 即时间复杂度为Ｏ(1) ⚫ 如果将s=0也看成是基本操作，则语句频度为 ２，其时间复杂度仍为Ｏ(1)，即常量阶。 ⚫ 例３、for(I=1;I<=n;++I) ⚫ {++x;s+=x;} ⚫ 语句频度为：2n 其时间复杂度为：O(n) ⚫ 即时间复杂度为线性阶
。例4、for(I=1<=n;++ for(=1j<=n;++j) {++xs+=x;} 语句频度为:2n2 其时间复杂度为:O(n2) 即时间复杂度为平方阶。 定理:若A(n)=amnm+am1nm-1+..+a1n+a0是 个m次多项式,则A(n)=O(nm) 证略 例5for(i=2;i<=n;++1) for(=2j<=i-1;++j 1++x; ai,j=X
⚫ 例４、for(I=1;I<=n;++I) ⚫ for(j=1;j<=n;++j) ⚫ {++x;s+=x;} ⚫ 语句频度为：2n2 ⚫ 其时间复杂度为：O(n2 ) ⚫ 即时间复杂度为平方阶。 ⚫ 定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是 一个m次多项式，则A(n)=O(n m) 证略。 例５for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i，j]=x;}
语句频度为: 1+2+3+…+n-2=(1+n-2)×(n-2)2 =(n-1)(n-2)2 =n2-3n+2 时间复杂度为O(m2) 即此算法的时间复杂度为平方阶 个算法时间为O(1)的算法,它的 基本运算执行的次数是固定的。因此, 总的时间由一个常数(即零次多项式) 来限界。而一个时间为O(n2)的算法则由 次多项式来限界
⚫ 语句频度为： ⚫ 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 ⚫ =(n-1)(n-2)/2 ⚫ =n2-3n+2 ⚫ ∴时间复杂度为O(n2) ⚫ 即此算法的时间复杂度为平方阶. ⚫ 一个算法时间为O(1)的算法，它的 基本运算执行的次数是固定的。因此， 总的时间由一个常数（即零次多项式） 来限界。而一个时间为O(n2)的算法则由 一个二次多项式来限界。 ⚫