時(shí)間復(fù)雜度--經(jīng)典解說(shuō)(編輯修改稿)
2025-01-23 22:23 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 中，調(diào)用次數(shù)為二叉樹(shù)的深度。 2. O(n): 表示該算法是線性算法 目前所學(xué)的算法中有：線性選擇算法 int Select(int data[],int p,int r,int k) { if(pr) return 1。 //p不能大于 r if(p==r) return data[p]。 //pr int s=partion(data,p,r)。 基本操作 if (s==k) return data[s]。 else if(sk) { int r1= Select(data,p,s1,k)。遞歸調(diào)用 return r1。 } else //sk { int r1=Select(data,s+1,r,ks)。遞歸調(diào)用 return r1。 } } 如果遞歸調(diào)用，每次規(guī)模是原來(lái)的 1/2： ??? ?????1)1()2/(11)(nnnTnnT因?yàn)槊恳淮我?guī)模都減到原來(lái)的 1/2，所以用換名的方法設(shè) n = 2k： T(n) = T(n/2) + (n1) = T(2k1) + (2k1) =[T(2k2) + (2k11)]+ (2k1) =… =[T(2kk) + (211)] + … +(2 k11) +(2k1) =T(1)+[(2k+12)k] =2nlogn1 算法時(shí)間復(fù)雜度： O(n) 分析： ??? ?????1)1()2/(11)(nnnTnnT算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是： logn，合并的復(fù)雜度是 n。 (nlogn) 所學(xué)過(guò)的算法：快速排序、堆排序等，分治法中的平面中最接近點(diǎn)對(duì)問(wèn)題。 遞推關(guān)系式： ??????)()2/(2)(1)2(nOnTnTT T(n)=2T(n/2) +n 設(shè) n= 2k =2T(2k1)+2k =2[2T(2k2)+2k1]+2k =22T(2k2)+2*2k =… =2k1T(2k(k1)) + (k1)*2k =n/2 + (logn1) *n 不失一般性，設(shè)規(guī)模為 n的問(wèn)題，每一次有分解為 m個(gè)子問(wèn)題，設(shè) n =mk，則： ??????)()/()(1)1(nOmnmTnTT T(n)=mT(n/m) +n =mT(mk1)+mk =m[mT(mk2)+mk1]+mk =m2T(mk2)+2*mk =… =mkT(2kk) + k*mk =n + logn *n 算法時(shí)間復(fù)雜度： O(nlogn) 分析： 算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是： n，合并的復(fù)雜度是 nlogn。 ??????)()/()(1)1(nOmnmTnTT 4. O(n2) 通常的兩層嵌套循環(huán)，內(nèi)層的運(yùn)算執(zhí)行次數(shù)，學(xué)過(guò)的例子有：比賽日程 ???????1)2/(*3)2/(11)( 2nnnTnnT T(n)=T(n/m)+(n/m)2 設(shè) n=mk =T(mk1)+m2(k1) =[T(mk2)+m2(k2) ]+ m2(k1) =… =[T(mkk)+m0]+… + m 2(k2)+m2(k1) =1+(m2k1)/(m21) =(n21)/(m21)+1 所以： O(n2) (nk) 所學(xué)過(guò)的：大整數(shù)乘法 Recursive_Miltiply(x,y) { if n=1 if (X=1)and(Y=1) return(1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1