●(4)效率与存储量需求效率指的是算法执行的 时间;存储量需求指算法执行过程中所需要的 最大存储空间。一般,这两者与问题的规模有 关。 1.4.3算法效率的度量 ●对一个算法要作出全面的分析可分成两用人 才个阶段进行,即事先分析和事后测试 事先分析求出该算法的一个时间界限函数 事后测试收集此算法的执行时间和实际占用 空间的统计资料 定义:如果存在两个正常数c和n,对于所有的 n三n,有|f(n)|c|g(n) ●则记作f(n)=O(g(m)
⚫ (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(=1,I<=mn;+D for(=1j<=n;++j) c[=0 for(k-l; 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{++xs=0;} 将x自增看成是基本操作,则语句频度为1 即时间复杂度为O(1) ●如果将s=0也看成是基本操作,则语句频度为 2,其时间复杂度仍为O(1),即常量阶。 ●例3、for(I=1;<=n;++ +:S+=X ●语句频度为: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;} 语句频度为:2n 其时间复杂度为:O 即时间复杂度为平方阶 定理:若A(n)= a mn m+am1nm1+.+a1n+a0是 个m次多项式,则A(n)=O(nm) 证略。 例5for(=2;<=n;++ for(=2j<=i-1;++j) R++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 ∷时间复杂度为Om2) 即此算法的时间复杂度为平方阶 个算法时间为O(1)的算法,它的 基本运算执行的次数是固定的。因此, 总的时间由一个常数(即零次多项式) 来限界。而一个时间为Om2)的算法则由 个二次多项式来限界
⚫ 语句频度为： ⚫ 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)的算法则由 一个二次多项式来限界。 ⚫