《算法分析与设计分治法ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计分治法ppt课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计分治法ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第二章第二章 分治法分治法什么是分治法？什么是分治法？二分检索二分检索找最大和最小元素找最大和最小元素归并分类归并分类快速分类快速分类选择问题选择问题斯特拉森矩阵乘法斯特拉森矩阵乘法2.1 分治法的一般方法分治法的一般方法问题(N个输入)子问题1子问题2子问题k子问题1子问题2子问题k相同的类型不用再分就可求解合并分治策略分治策略DANDC的抽象化控制的抽象化控制Procedure DA
2、NDC(p,q)global n,A(1:n);integer m,p,q;/1pqn/if SMALL(p,q)then return(G(p,q)else mDIVIDE(p,q)/pmq/return(COMBINE(DANDC(p,m),DANDC(m+1,q)endifEnd DANDC判断输入规模判断输入规模q-p+1是否足够的小是否足够的小求解该规模问题解的函数求解该规模问题解的函数将两个子问题的解合成原问题将两个子问题的解合成原问题分割函数分割函数分治策略分治策略DANDC的计算时间的计算时间倘若所分成的两个子问题的输入规模大致相等，倘若所分成的两个子问题的输入规模大致相等，则
3、分治策略则分治策略DANDC的计算时间可表示为：的计算时间可表示为：T(n)=g(n)n足够小足够小2T(n/2)+f(n)否则否则说明：说明：T(n)是输入规模为是输入规模为n的分治策略的计算时间的分治策略的计算时间 g(n)是对足够小的输入规模能直接计算出答案的时间是对足够小的输入规模能直接计算出答案的时间 f(n)是是COMBINE解合成原问题的计算时间解合成原问题的计算时间2.2 二分检索二分检索问题描述问题描述n已知一个按已知一个按非降次序排列非降次序排列的元素表的元素表a1,a2,an，判定某个给定元素，判定某个给定元素x是否在该表是否在该表中出现，若是，则找出该元素在表中的位置，
4、中出现，若是，则找出该元素在表中的位置，并置于并置于j，否则，置，否则，置j为为0。一般解决方法一般解决方法（从头到尾查找一遍）（从头到尾查找一遍）a1a2a3a4anx成功和不成功的计算时间都是成功和不成功的计算时间都是n 二分检索原理二分检索原理将问题表示为：将问题表示为：I=(n,a1,an,x)选取一个下标选取一个下标k，可得到三个子问题：，可得到三个子问题：I1=(k-1,a1,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,an,x)如果对所求解的问题（或子问题）所选的下标如果对所求解的问题（或子问题）所选的下标k都是中间元素的下标，都是中间元素的下标，k=(n+1)
5、/2，则由，则由此产生的算法就是此产生的算法就是二分检索算法二分检索算法。二分检索算法二分检索算法Procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1;highn if(n0)while（lowhigh）do mid(low+high)/2 /*取中间值*/case xAmid:lowmid+1 /*寻找后一半*/else:jmid ;return /*检索成功*/endcase j0 /*检索失败*/End BINSRCH二分检索算法实例二分检索算法实例假设在数组假设在数组A(1:9)中顺序放了以下中顺序放了以下9个元素：个元素：-1
6、5,-6,0,7,9,23,54,82,101要求检索的要求检索的x分别为：分别为：101,-14,82X=101Lowhighmid195697898999OKX=-14Lowhighmid195142111 2 1NOX=82Lowhighmid195697898OK二分检索算法正确性的证明二分检索算法正确性的证明用五个特性判断是否是一个算法用五个特性判断是否是一个算法n根据算法的描述，满足五个特性的才是算法根据算法的描述，满足五个特性的才是算法证明算法是否正确证明算法是否正确n如果如果n=0，则不进入循环，则不进入循环，j=0，算法终止，算法终止n否则就会进入循环与数组否则就会进入循环与
7、数组A中的元素进行比较中的元素进行比较n如果如果x=Amid，则，则j=mid，检索成功，算法终止，检索成功，算法终止n否则，若否则，若xA(mid)，则缩小到，则缩小到A(mid+1)和和A(n)之间检索之间检索n按上述方式缩小检索区总可以在有限步内使按上述方式缩小检索区总可以在有限步内使lowhighn如果出现这种情况，说明如果出现这种情况，说明x不在不在A中，中，j=0，算法终止，算法终止二分检索算法所需的空间和时间二分检索算法所需的空间和时间所需空间所需空间n用用n个位置存放数组个位置存放数组A，还有，还有low,high,mid,x,j五个变量需要存储，五个变量需要存储，共需空间共需
8、空间n+5计算时间计算时间n对于计算时间，需要分别考虑以下几种情况：对于计算时间，需要分别考虑以下几种情况：w成功检索的最好情况和不成功检索的最好情况成功检索的最好情况和不成功检索的最好情况w成功检索的平均情况和不成功检索的平均情况成功检索的平均情况和不成功检索的平均情况w成功检索的最坏情况和不成功检索的最坏情况成功检索的最坏情况和不成功检索的最坏情况成功检索最好情况和不成功检索最好情况成功检索最好情况和不成功检索最好情况成功的检索共有成功的检索共有n种种不成功的检索共有不成功的检索共有n+1种种A(1)(2)(3)(4)(5)(6)(7)(8)(9)元素-15-6079235482101比较
9、次数3234132343334433344不成功的检索成功的检索二元比较树572134689内结点内结点,表示表示一次元素的一次元素的比较比较,存放已存放已个个mid值值外结点外结点,表示不成功表示不成功检索的一种情况检索的一种情况每一条路径表每一条路径表示一个元素的示一个元素的比较序列比较序列9-6-1505472382101二分检索的时间复杂度二分检索的时间复杂度定理定理2.2：若：若n在区域在区域2k-1,2k)中，则对于一次成功的检中，则对于一次成功的检索，二分检索索，二分检索至多至多作作k次比较，次比较，至少至少作作1次比较；而对于次比较；而对于一次不成功的检索，或者作一次不成功的检
10、索，或者作k-1次比较或者作次比较或者作k次比较。次比较。证明证明 考察以n个结点描述BINSRCH执行过程的二元比较树，所有成功检索都在内部结点处结束，而所有不成功检索都在外部结点处结束。由于n在区域2k-1,2k)中，因此，所有的内部结点在1，2，k级，而所有的外部结点在k和k+1级（根在1级）。就是说，成功检索在i级终止所需要的元素比较数是i，而不成功检索在i级外部结点终止的元素比较数是i-1。二分检索的时间复杂度二分检索的时间复杂度最坏情况下的成功检索计算时间最坏情况下的成功检索计算时间(logn)最坏情况下的不成功检索计算时间最坏情况下的不成功检索计算时间(logn)最好情况下的成功
11、检索计算时间最好情况下的成功检索计算时间(1)最好情况下的不成功检索计算时间最好情况下的不成功检索计算时间(logn)每种不成功的检索时间都为每种不成功的检索时间都为(logn)成功检索的平均比较次数由根到所有内部结点的距离之和称为内部路径长度I;由根到所有外部结点的距离之和称为外部路径长度E;E=I+2n令S(n)是成功检索的平均比较次数。找一个内部结点表示的元素所需的比较次数是由根到该结点的路径长度（即距离）加1。因此，S(n)=I/n+1到一个外部结点所需要的比较数是由根到该结点路径的长度。因此，U(n)=E/(n+1)由以上各公式可得 S(n)=(1+1/n)U(n)-1由于U(n)=
12、(logn)，所以成功检索的计算时间S(n)也为(logn)二分检索在各种情况下的检索时间二分检索在各种情况下的检索时间计算时间最好平均最坏成功的检索(1)(logn)(logn)不成功的检索(logn)(logn)(logn)以比较为基础检索的时间下界以比较为基础检索的时间下界有有n个如下关系的元素个如下关系的元素:A(1)A(2)A(n),检索一给定检索一给定元素元素X是否在是否在A中出现中出现X:A(1)X:A(2)X:A(n)不成功不成功不成功不成功线性检索线性检索二分检索二分检索X:A(n+1)/2)X:A(3n+1)/4)X:A(n+1)/4)X:A(n)X:A(2n+1)/2+1
13、)X:A(2n+1)/2-1)X:A(1)不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功不成功以比较为基础检索的时间下界以比较为基础检索的时间下界定理定理2.3：设：设A(1:n)含有含有n(n1)个不同的元素，排序为个不同的元素，排序为A(1)A(2)max then maxAi endif if Aimax then maxAiElse if(Aimin then minAi endifendif算法的时间复杂度算法的时间复杂度改进前：改进前：2(n-1)改进后：最好改进后：最好n-1，最坏，最坏2(n-1)，平均，平均3(n-1)/2可考虑用分
14、治策略来解决这个问题可考虑用分治策略来解决这个问题将任一实例将任一实例I=(n,A(1),A(n)分成一些较小的实例来分成一些较小的实例来处理。处理。I=(n,A(1),A(n)I1=(n/2,A(1),A(n/2)I2=(n-n/2,A(n/2+1),A(n)递归求取最大和最小元素递归求取最大和最小元素Procedure MAXMIN(i,j,fmax,fmin)integer i,j;global n,A(1:n)case :i=j:fmaxfminA(i):i=j-1:if A(i)2当当n=2k(k是某个正整数是某个正整数)时，有时，有T(n)=3n/2-2T(n)=2T(n/2)+2
15、=4T(n/4)+4+2=2k-1T(2)+(2+22+2i+2k-1)=2k-1+2k-2=3n/2-2 当n2时 与直接算法的比与直接算法的比较次数较次数2(n-1)相比，比较次数相比，比较次数减少了减少了25%。MAXMIN算法分析算法分析由于递归的调用，由于递归的调用，MAXMIN所需要的存储空间较多，递所需要的存储空间较多，递归调用也消耗了部分时间。归调用也消耗了部分时间。元素元素A(i)和和A(j)的比较与的比较与i和和j的比较时间相差不大时，过的比较时间相差不大时，过程程MAXMIN不可取。如果设过程不可取。如果设过程MAXMIN的频率计数为的频率计数为C(n)，n=2k，k是一
16、个整数，并用是一个整数，并用i=j-1来代替来代替i=j和和i=j-1，有：，有：C(n)2n=22C(n/2)+3 n2当n2时，C(n)=2C(n/2)+3 =4C(n/4)+6+3 =2k-1C(2)+3(1+2+22+2i+2k-2)=2k+3*2k-1-3 =5n/2-3 当当n较大时，比较次数会远远大于直接比较算法较大时，比较次数会远远大于直接比较算法结论：如果数组结论：如果数组A的元素的元素间的比较远比整型变量间的比较远比整型变量的比较代价昂贵，则分的比较代价昂贵，则分治法产生效率较高的算治法产生效率较高的算法；反之，就得到一个法；反之，就得到一个效率较低的程序。效率较低的程序。
17、2.4 归并分类（排序）归并分类（排序）问题描述问题描述 给定一个含有给定一个含有n个元素个元素(或叫关键字或叫关键字)的集合，把它们按一的集合，把它们按一定的次序分类定的次序分类(如非降次序排序如非降次序排序)一般方法一般方法(插入法插入法)For j2 to n do 将将A(j)放到已分类集合放到已分类集合A(1:j-1)的正确位置上的正确位置上Repeat插入分类算法描述插入分类算法描述Procedure INSERTIONSORT(A,n)A(0)-for j2 to n do itemA(j);ij-1 while itemA(i)do A(i+1)A(i);ii-1 repeat
18、 A(i+1)item repeatEnd INSERTIONSORT数组元素数组元素的移动的移动插入排好插入排好序的值序的值可能执行可能执行0j 次次(j=2,3n)最坏情况的计算时间：最坏情况的计算时间：2+n=(n(n+1)/2)-1=(n2)，最好情况，最好情况(n)分治策略设计分类算法分治策略设计分类算法I=(n,A(1),A(n)I1=(n-n/2,A(1),A(n/2)I2=(n-n/2,A(n/2+1),A(n)I=(n,A(1),A(n)MERGEProcedure MERGESORT(low,high)interger low,high if lowmid then for
19、 kj to high do B(i)A(k);ii+1 repeat else for kh to mid do B(i)A(k);i i+1 repeat end if for klow to high do A(k)B(k)repeatEnd MERGE处理两个已分类的序列处理两个已分类的序列剩余元素的处理过程剩余元素的处理过程将已分类的集合复制到将已分类的集合复制到A数组数组归并分类算法实例归并分类算法实例310 285 179 652 351 423 861 254 450 520285 310 179 652 351 423 861 254 450 520179 285 310 6
20、52 351 423 861 254 450 520 179 285 310 351 652 423 861 254 450 520179 285 310 351 652 423 861 254 450 520归并分类算法实例归并分类算法实例179 285 310 351 652 423 861 254 450 520179 285 310 351 652 254 423 450 520 861反复递归调用，合并反复递归调用，合并179 254 285 310 351 423 450 520 652 861合并合并MERGESORT调用树调用树1,106,101,51,34,56,89,108
21、,89,910,105,54,43,31,26,71,12,27,76,6表示一次调表示一次调用时的用时的low和和high的值的值只含单个元只含单个元素的子集合素的子集合将问题不断分解成规将问题不断分解成规模较小的子问题，使模较小的子问题，使之更容易解决。之更容易解决。MERGE调用树调用树1，1，24，4，56，6，71，2，39，9，106，7，86，8，101，3，51，5，10表示一次表示一次MERGE调用时的调用时的low,mid,high值值表示表示A(1:3)和和A(4:5)中中的元素归并的元素归并将处理好的子问题将处理好的子问题不断的合并，最终不断的合并，最终获得原问题的结果
22、获得原问题的结果归并分类的计算时间归并分类的计算时间T(n)=a n=1,a是常数是常数2T(n/2)+cn n1,c是常数是常数当当n=2k时，可得时，可得T(n)=2(2T(n/4)+cn/2)+cn =22T(n/4)+2cn =4(2T(n/8)+cn/4)+2cn =23T(n/8)+3cn =2kT(1)+kcn =an+cnlogn如果如果2kn2k+1，有，有T(n)T(2k+1)，有，有T(n)=O(nlogn)改进的分类归并算法procedure MERGESORT1(low,high,p)/利用辅助数组LINK(low:high)将全程数组A(low:high)按非降次序
23、分类。LINK中值表示按分类次序给出A下标的表，并把p置于指示这表的开始处/global A(low:high),LINK(low:high)if high-low+116then call INSERTIONSORT(A,LINK,low,high,p)else mid-(low+high)/2 call MERGESORT1(low,mid,q)call MERGESORT1(mid+1,high,r)call MERGE1(q,r,p)endifend MERGESORT1任何以关键字比较为基础的分类算法，最坏情任何以关键字比较为基础的分类算法，最坏情况下的时间下界都是况下的时间下界都是
24、(nlogn)，因此，从数量，因此，从数量级的角度上来看，归并算法是最坏情况下的最级的角度上来看，归并算法是最坏情况下的最优算法。优算法。下面用二元比较树给出以比较为基础的分类算下面用二元比较树给出以比较为基础的分类算法时间下界的证明。法时间下界的证明。以比较为基础分类的时间下界以比较为基础分类的时间下界关键字分类的二元比较树关键字分类的二元比较树1:21:31:32:32:31,2,31,3,23,1,22,1,32,3,13,2,1A(1)A(2)A(2)A(3)A(1)A(3)A(2)A(3)A(1)A(3)表示一表示一次比较次比较一种可能的一种可能的分类序列分类序列以比较为基础分类的时
25、间下界以比较为基础分类的时间下界由于由于n个关键字有个关键字有n!种排列，而每种排列可以是某种特定输入下种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有的分类结果，因此比较树必定至少有n!个外结点，每个外结点表个外结点，每个外结点表示一种可能的分类序列。示一种可能的分类序列。对于任何一个以比较为基础的算法，在描述其执行的那棵比较树对于任何一个以比较为基础的算法，在描述其执行的那棵比较树中，中，由根到某外结点的路径长度表示生成该外结点中那个分类序由根到某外结点的路径长度表示生成该外结点中那个分类序列所需要的比较次数。列所需要的比较次数。从而，要求出所有以比较为基础的对从而，
26、要求出所有以比较为基础的对n个个关键字分类的算法最坏情况下界，只需求出这些算法对应的比较关键字分类的算法最坏情况下界，只需求出这些算法对应的比较树的最小高度。树的最小高度。据二元树的性质可知，如果一棵二元树的所有内结点的级数均小据二元树的性质可知，如果一棵二元树的所有内结点的级数均小于或等于于或等于k，则该树至多有，则该树至多有2k个外结点（比内结点数多个外结点（比内结点数多1）。）。令令T(n)=k，则，则n!1时有时有n!=n(n-1)(n/2)=(n/2)n/2因此，对于因此，对于n=4有有 T(n)=(n/2)log(n/2)=(n/4)logn。故以比较为基础的分类算法的最坏情况的时
27、间下界为故以比较为基础的分类算法的最坏情况的时间下界为(nlogn)2.5快速分类（排序）Procedure QUICKSORT(p,q)integer p,q;global n,A(1:n)if p=v repeat loop p=p-1 until A(p)=v repeat if ip then call INTERCHANGE(A(i),A(p)else exitRepeatA(m)=A(p);A(p)=vEnd PARTITIONPARTITION算法实例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)i p 65 45 50 55 60 85 80 75 70 +6
28、5 65 45 75 80 85 60 55 50 70 +3 8 65 45 50 80 85 60 55 75 70 +4 7 65 45 50 55 85 60 80 75 70 +5 6 65 70 75 80 85 60 55 50 45 +2 9 60 45 50 55 65 85 80 75 70 +QUICKSORT算法分析假设参加分类的n个元素各不相同;PARTITION中的划分元v是随机选取的.要分析QUICKSORT,只需计算出它的元素比较次数C(n)即可.令C(n)在最坏情况下的值为CW(n),易知CW(n)=O(n2)令C(n)在平均情况下的值为CA(n),则CA(n
29、)=n+1+1/ni k n(CA(k-1)+CA(n-k)CA(n)2(n+1)loge(n+1)=O(nlogn)QUICKSORT算法分析最坏情况：O(n2)平均情况：O(nlogn)2.6 选择问题2.6.1 选择问题算法(找第K小元素)Procedure SELECT(A,n,k)integer n,k,m,r,j;m=1;r=n+1;A(n+1)=+;Loop j=r;call PARTITION(m,j)case :k=j:return :kj:r=j :else:m=j+1 endcaseEnd SELECT最坏情况：O(n2)平均情况：O(n)2.6选择问题（续）最坏情况时间
30、是O(n)的选择算法采用二次取中值规则选取划分元素二次取中值规则选取划分元素例：设 n=35,r=7。n分为n/r=5个元素组：B1，B2，B3，B4，B5；每组有7个元素。nB1-B5按照各组的mi的非增次序排列。n mm 为各 mi的中间值，1i5。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列二次取中值规则选取划分元素 由于由于r个元素的个元素的中间值中间值是第是第 小元素。则，小元素。则，至少有至少有 个个mi小于或等于小于或等于mm；至少有至少有 个个mi大于或等于大于或等于mm。则，至少有则，至少有 个元素小于或等于（或大于
31、或等于）个元素小于或等于（或大于或等于）mm。当当r=5，则使用两次取中间值规则来选择，则使用两次取中间值规则来选择v=mm，可推出，可推出，至少有至少有 个元素小于或等于选择元素个元素小于或等于选择元素v。至多有至多有 个元素大于个元素大于v。至多有至多有 0.7n+1.2个元素小于个元素小于v。故，这样的故，这样的v可可近似平均近似平均地划分地划分A中的中的n个元素。个元素。使用二次取中规则的选择算法Procedure SELECT2(A,k,n)1 若n=r，则采用插入法直接对A分类并返回第K小元素。2 把A分成大小为r的n/r个子集合，忽略剩余的元素。3 设mm1,m2,mn/r是上面
32、n/r个子集合的中间值的集合4 v=SELECT2(m,n/r/2,n/r)5 用PARTITION划分A，v作为划分元素。6 假设v在位置j。7 case :k=j:return(v):k=24时由此得：T(n)=1时 T(n)=k:return(SELECT2(S,k,|S|):|S|+|U|=k:return(v):else:return(SELECT2(R,k-|S|-|U|,|R|)Endcase修改后的SELECT2 的时间复杂度仍是O(n)SELECT2的的SPARKS的描述算法的描述算法procedure SEL(A,m,p,k)/返回一个返回一个i，使得，使得im,p，且，且
33、A(i)是是A(m:p)中第中第k小元素，小元素，r是一个全程变量，其取值为大于是一个全程变量，其取值为大于1的整数的整数 global r;integer n,i,j if p-m+1r then call INSERTIONSORT(A,m,p);return(m+k-1);endif loop np-m+1/元素数元素数/for i1 to n/r do /计算中间值计算中间值/call INSERTIONSORT(A,m+(i-1)*r,m+i*r-1)/将中间值收集到将中间值收集到A(m:p)的前部的前部/call INTERCHANGE(A(m+i-1),A(m+(i-1)r+r/
34、2-1)repeat jSEL(A,m,m+n/r-1,n/r/2)/mm/call INTERCHANGE(A(m),A(j)/产生划分元素产生划分元素/jp+1 call PARTITION(m,j)case :j-m+1=k:return(j):j-m+1k:pj-1 :else:kk-(j-m+1);mj+1 endcase repeat end SEL2.7斯特拉森矩阵乘法令A和B为nn的矩阵，则：由矩阵加定义直接产生的矩阵加算法的时间为O(n2)由矩阵乘定义直接产生的矩阵乘算法的时间为O(n3)用分治法解决矩阵相乘令n=2k，按照分治法，可将A和B都分成四个(n/2)(n/2)矩阵
35、，可得：A11 A12 B11 B12 C11 C12 A21 A22 B21 B22 C21 C22其中：C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22分治算法的时间T(n)b n2 求解这个递归式得T(n)=O(n3)，与通常的矩阵算法计算时间具有相同的数量级。Strassen矩阵乘法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A22(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)
36、(B21+B22)C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+U以上共用了7次乘法和18次加（减）法。Strassen矩阵乘法分析T(n)所得出的递归关系式是：b n2求解这个递归关系式，得T(n)O(n2.81)矩阵乘法的时间复杂性有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非能找到一种计算2阶方阵乘积的算法，使乘法的计算次数少于7次，按上述思路才有可能进一步改进矩阵乘积的计算时间的上界。但是Hopcroft 和 Kerr(197l)已经证明，计算2个22矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不
37、能再寄希望于计算22矩阵的乘法次数的减少。或许应当研究33或55矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界(n2)。课后思考题课后思考题给你一个装有给你一个装有n个硬币的袋子。个硬币的袋子。n个硬币个硬币中有一个是伪造的，并且那个伪造的硬中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算法的思想写出解决问题的算法，并计算其时间复杂度。其时间复杂度。