實(shí)現(xiàn)函數(shù)double Power(double base, int exponent)拘央，求base的exponent次方滔悉。不得使用庫函數(shù)向叉，同時(shí)不需要考慮大數(shù)問題又跛。
題目規(guī)定不能使用庫函數(shù)伪窖，馬上想到了循環(huán)n次逸寓。每次乘以 base得到結(jié)果。
算法一：
func myPow(_ x: Double, _ n: Int) -> Double {
var res = 1.0
for _ in 0..<n {
res *= x
}
return res
}
以為就這么簡單啦覆山？拿到上面的代碼到力扣上面提交竹伸，很快就會(huì)報(bào)錯(cuò)，因?yàn)槲覀儧]有考慮到各種邊界條件簇宽。這也是這道題目所要考察的地方勋篓。開發(fā)人員考慮邊界條件。上面代碼只考慮了 base晦毙、exponent都正常的情況生巡。base、exponent為 0 或者是負(fù)數(shù)的情況都沒有考慮到见妒。
算法一改良版：
func myPow(_ x: Double, _ n: Int) -> Double {
if x == 0 && n < 0 {
fatalError("參數(shù)輸入有誤")
}
if n == 0 {
return 1
}
let m = (n > 0) ? n : -n
var res = 1.0
for _ in 0..<m {
res *= x
}
return n > 0 ? res : 1/res
}
改良版后的算法已經(jīng)滿足了我們的算法要求孤荣，能夠得到正確的答案了，但是提交到力扣上還是會(huì)因算法的時(shí)間復(fù)雜度問題超時(shí)须揣，所以我們還需要優(yōu)化盐股。
要求一個(gè)數(shù)值的n次方時(shí)，我們只需要對(duì)數(shù)值的n/2次方進(jìn)行一次平方就能夠得到耻卡。如數(shù)值的16次方疯汁，可以轉(zhuǎn)換為數(shù)值8次方的平方，依次推出：8次方的需要4次方的平方卵酪。4次方需要的是2次方的平方幌蚊。這樣大大的降低了我們循環(huán)的次數(shù)谤碳。(PS:如果所求是奇次方，可以將exponent-1溢豆，轉(zhuǎn)換為偶次方后再乘以 base)
算法二：
func myPow(_ x: Double, _ n: Int) -> Double {
if x == 0 && n < 0 {
fatalError("參數(shù)輸入有誤")
}
if n == 0 {
return 1
}
if n == 1 {
return x
}
var n = n
var x = x
var res = 1.0
if n < 0 {
n = -n
x = 1/x
}
while n > 0 {
if n & 1 == 1 {
res *= x
}
print(res)
n = n >> 1
x *= x
}
return res
}
