分治法求冪,分治法求a的n次方.pdf

《分治法求冪,分治法求a的n次方.pdf》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、分治法求a的n次方a.如果n是偶數(shù),那么??=??/?×??/?如果n是奇數(shù),那么??=??/?×??/?×?這樣一直遞歸下去,直到?=?,直接返回?即可。算法偽代碼:DE_POW(a,n)://遞歸計算??的值//輸入：底數(shù)a,指數(shù)n//輸出：??的值ifn=1returnaelseifn%2=0:temp=DE_POW(a,n/2)returntemp?tempelse:temp=DE_POW(a,(n?1)/2)1/2returntemp?temp?ab.當輸入的n=2?時，有nT(n)=T()+1,T(1)=02則T(n

2、)=T(2??1)+1=T(2??2)+2…=T(1)+k帶入k=???2?解得T(n)=???2?c.蠻力法就是一個循環(huán)做n-1次乘法求??的值，分治算法DE_POW時間效率為Θ(logn)而蠻力法效率為Ο(n).2/2