4、算法和算法分析 算法的时间复杂度: 原操作指对固有数据类型的操作 个算法由控制结构和原操作构成,我们用对所研究的问 题来说是基本操作的原操作的重复执行次数作为算法时间复杂 度的量度 最基本操作是比较操作,外循环执行n-1次, 【例】 内循环平均执行(1+2+.+n-1)(n-1)=n/2次,总 的比较次数是T(n)=(n-1)*n/2,它是问题规模n void selector(int rl,int n)的函数 f int temp; int i,j, k 在数据结构中,常常将复杂度记做O(f(n) for(i=0:i<n-1:i++)当n>=m时,T(n)<=cn,及T(n)是fn)的常数倍 i ki 也就是说,当n足够大时,T(n)和(n)具有相同 的增长率。因此,在数据结构中,常常用Ofn) for(-+1j<m++)表示复杂度。左例的时间复杂度可以记做On2 rlilsrk)k=j;)实际上就是on if(i:=ktemp-=r;r=rk;rk=temp; 1 EpEe d?典4、算法和算法分析 • 算法的时间复杂度： 一个算法由控制结构和原操作构成，我们用对所研究的问 题来说是基本操作的原操作的重复执行次数作为算法时间复杂 度的量度。 【例】 void selector(int r[],int n) { int temp;int i,j,k for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(r[j]<r[k]) k=j; if(i!=k){temp=r[i];r[i]=r[k];r[k]=temp;} } } 原操作指对固有数据类型的操作 最基本操作是比较操作，外循环执行n-1次， 内循环平均执行(1+2+…+n-1)/(n-1)=n/2次，总 的比较次数是T(n)=(n-1)*n/2，它是问题规模n 的函数。 在数据结构中，常常将复杂度记做O(f(n))。 当n>=n0时，T(n)<=cf(n)，及T(n)是f(n)的常数倍。 也就是说，当n足够大时，T(n) 和f(n)具有相同 的增长率。因此，在数据结构中，常常用O(f(n)) 表示复杂度。左例的时间复杂度可以记做O(n2 - n)，实际上就是O(n2 )