时间复杂度解说专业知识讲座.ppt

本文档所提供的信息仅供参考之用，不能作为科学依据，请勿模仿。文档如有不 当之处，请联系本人或网站删除。 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 , 用反向替换法对它求解： 58 . 1 3 l og l og 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. 对于输入特性的差异，我们将从数学上 进行精确分析并带入函数解析式。 本文档所提供的信息仅供参考之用，不能作