时间复杂度 经典解说.pptVIP

T(n)=mT(n/m) +n =mT(m k-1 )+m k =m[mT(m k-2 )+m k-1 ]+m k =m 2 T(m k-2 )+2*m k =… =m k T(2 k-k ) + k*m k =n + logn *n 算法时间复杂度： O(nlogn) 分析： 算法的复杂度有两部分决定：递归和合并， 递归的复杂度是： n ，合并的复杂度是 nlogn 。 ? ? ? ? ? ? ) ( ) / ( ) ( 1 ) 1 ( n O m n mT n T T 4. O(n 2 ) 通常的两层嵌套循环，内层的运算执行 次数，学过的例子有：比赛日程 ? ? ? ? ? ? ? 1 ) 2 / ( * 3 ) 2 / ( 1 1 ) ( 2 n n n T n n T T(n)=T(n/m)+(n/m) 2 设 n=m k =T(m k-1 )+m 2(k-1) =[T(m k-2 )+m 2(k-2) ]+ m 2(k-1) =… =[T(m k-k )+m 0 ]+… + m 2(k-2) +m 2(k-1) =1+(m 2k -1)/(m 2 -1) =(n 2 -1)/(m 2 -1)+1 所以： O(n 2 ) 4.O(n k ) 所学过的：大整数乘法 Recursive_Miltiply(x,y) { if n=1 if (X=1)and(Y=1) return(1) else return(0) x 1 =X 的左边 n/2 位 ; x 0 =X 的右边 n/2 位 ; y 1 =Y 的左边 n/2 位 ; y 0 =Y 的右边 n/2 位 ; p = Recursive_Miltiply(x 1 +x 0 ,y 1 +y 0 ); —— 递归调用 x 1 y 1 = Recursive_Miltiply(x 1 ,y 1 ); —— 递归调用 x 0 y 0 = Recursive_Miltiply(x 0 ,y 0 ); —— 递归调用 return x 1 y 1 *2 n + (p-x 1 y 1 -x 0 y 0 )*2 n/2 +x 0 y 0 ; —— 基本操作 } ? ? ? ? ? ? ? 1 1 ) ( ) 2 / ( 3 ) 1 ( ) ( n n n O n T O n T k k k k i k i k k k T T T T T 3 ) 2 ( 3 ) 2 ( 3 ) 2 ( 3 ) 2 ( 3 ) 2 ( 2 2 1 ? ? ? ? ? ? ? ? ? ? ? 设， n=2 k , 用反向替换法对它求解： 585 . 1 3 log log 2 2 3 ) ( n n n T n ? ? ? 分析： 在这个递推关系式中，算法每次 递归调用 3 个规模为 1/2 的子问题，那 么总的规模 3/2 ，大小，所以，粗略估 算要在 O(nlogn) 、 O(n 2 ) 之间。 ? ? ? ? ? ? ? 1 1 ) ( ) 2 / ( 3 ) 1 ( ) ( n n n O n T O n T 时间复杂度分析 算法时间复杂度的数学意义 从数学上定义，给定算法 A ，如 果存在函数 f(n) ，当 n=k 时， f(k) 表示 算法 A 在输入规模为 k 的情况下的运行 时间，则称 f(n) 为算法 A 的时间复杂度。 其中：输入规模是指算法 A 所接受输入的自然独立体的 大小，我们总是假设算法的输入规模是用大于零的 整数表示的，即n=1,2,3,……,k,…… 对于同一个算法，每次执行的时 间不仅取决于输入规模，还取决于输入的特 性和具体的硬件环境在某次执行时的状态。 所以想要得到一个统一精确的 F(n) 是不可能 的。为此，通常做法： 1. 忽略硬件及环境因素，假设每次执 行时硬件条件和环境条件是完全一致的。 2. 对于输入特性的差异，我们将从数 学上进行精确分析并带入函数解析式。 例子： x=1; for(i=1;i=n;i++) for(j=1;j=i;j++) for(k=1;k=j;k++)