文档介绍：参考: 算法的时间复杂度分析 ?算法的空间代价( 或称空间复杂性) :当被解决问题的规模( 以某种单位计算)由1 增至 n 时,解该问题的算法所需占用的空间也以某种单位由f (1) 增至 f(n),这时我们称该算法的空间代价是 f(n)。?算法的时间代价( 或称时间复杂性) :当问题规模以某种单位由 1 增至 n 时,对应算法所耗费的时间也以某种单位由 g (1) 增至 g(n), 这时我们称该算法的时间代价是 g(n)。一般情况下,算法中基本操作重复执行的次数是问题规模 n的某个函数 f(n) ,算法的时间量度记作: T(n)=O(f(n)) 上式表示随问题规模 n的增大,算法执行时间的增长率和f(n) 的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。???? 3 3)(nOnT nnf??例:n×n矩阵相乘 for(i=1;i<=n;i++) n次 O(n *n*n) for(j=1;j<=n;j++) n次 O(n *n) {c[i][j]=0; for(k=1;k<=n;k++) n次 O(n) c[i][j]=c[i][j]+a[i][k] * b[k][j]; O(1) } 问题的规模、空间单位和时间单位?问题的规模一般可以根据问题本身的提法确定。例如对 n个记录进行排序,这里 n即可以作为问题的规模。?空间单位和时间单位没有统一的规定,通常取算法描述中的初等数据占用的空间和基本操作耗费的时间为单位。?一般,空间单位选择为一个简单变量(如整型或者实型等)所占存储空间的大小;时间单位则选择为执行一个简单语句(如赋值语句或者判断语句等)所用时间。?选择排序的时间代价(n -1)+ ( n -2)+ … + 1 = n? (n -1)/2 大O表示法?说某个算法的时间代价(或者空间代价)为 O(f(n )),如果存在正的常数 c和n0,当问题的规模 n≥n0后,该算法的时间(或空间)代价T(n)≤c·f(n)。?也称该算法的时间(或空间)代价的增长率为 f(n)。?例如,如果有 T(n ) = 3 n 3,很容易证明 T(n ) = O(n 3)。当然我们也可以证明 T(n ) = O(n 4)。但从分析的精度来看,前一结论给出的是上确界(上界中最小的),后者给出的仅是一般上界中的一个。大O运算的规则: 1、忽略常数因子。对于常数 K和函数 f(n) , kf(n )= O (f(n)) 2、如果 f(n)= O (g(n)) ,并且 g(n)= O (h(n)) 则 f(n)= O (h(n)) 3、 f(n)+g(n)= O (max(f(n),g(n)) 4、如果 f1(n)= O (g1(n)) ,并且 f2(n)= O (g2(n)) 则 f1(n) * f2(n)= O (g1(n) * (g2(n)) 以下六种计算算法时间的多项式是最常用的。其关系为: O(1)< O(logn )<O(n)< O(nlogn ) <O(n 2 )<O(n 3) 指数时间的关系为: O(2 n )<O(n!)< O(n n) c < log 2 n < n <n log 2 n< n 2 < n 3 < 10 n 原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。 O(n * n) n*n for(j=1;j<=n;++j) for(k=1;k<=n;++k) {++x;s+=x;} O(n) n for(i=1;i<=n;++i) {++x;s+=x;} O(1) 1 {++x;s=0;} 时间复杂度频度语句有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如: Void bubble_sort(int a[ ] , int n) for(i=n-1,change=TURE ; i>1 && change ; --i) { change=false; for(j =0;j< i;++j ) if (a[j]>a[j+1]) { a[j] ←→ a[j+1]; change=TURE;} } 这是一个起泡排序算法。最好情况:f(n)=0 最坏情况:f(n)= 1+2+3+ …+n-1 =n(n-1)/2 T(n)=O(n 2) 在最坏情况下基本操作执行次数最坏情况下时间复杂度依基本操作执行次数概率计算平均平均时间复杂度基本操作的执行