時(shí)間復(fù)雜度分析(編輯修改稿)
2024-09-03 11:21 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ==A[i]) return i。 else return 0。 } else { int mid=(i+n)/2。 if(x==A[mid]) return mid。 基本操作 else if(xA[mid]) return BinSrh(A, i, mid1, x)。—— 遞歸調(diào)用 else if(xA[mid]) return BinSrh(A, mid+1, n, x)。—— 遞歸調(diào)用 } } 遞歸關(guān)系式： 11??nn????? 1)2/(1)(nCnC因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來(lái)的 1/2，所以采用換名方法求解，設(shè) n = 2k： C(n) = C(2k)= C(2k1)+1 = C(2k2) + 2 =… =C(2kk)+k =C(1) + k = logn+1 3 9 17 21 34 57 69 84 92 10 3 9 17 21 57 69 84 92 10 3 17 21 57 69 92 10 69 10 21 觀察遞歸調(diào)用的過(guò)程以及遞推關(guān)系式： （ 1）在遞歸關(guān)系式中：遞歸調(diào)用共有 k次，我們?cè)O(shè) n= 2k， k=logn （ 2）遞歸調(diào)用的二叉樹(shù)型結(jié)構(gòu)中，調(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)] + … +(2k11) +(2k1) =T(1)+[(2k+12)k] =2nlogn1 算法時(shí)間復(fù)雜度： O(n) 分析： ????????1)1()2/(11)(nnnTnnT算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1