思想與特性
分治（分而治之）斑鼻，分治法將原問(wèn)題劃分為若干規(guī)模較小且結(jié)構(gòu)與原問(wèn)題相同或相似的子問(wèn)題，分別解決子問(wèn)題猎荠，最后合并其問(wèn)題的解坚弱，即可得到原問(wèn)題的解。
- 子問(wèn)題應(yīng)當(dāng)是相互獨(dú)立关摇，沒(méi)有交叉的荒叶。
- 分治到一定小規(guī)模的子問(wèn)題可解
- 分治常用遞歸實(shí)現(xiàn)，也可以非遞歸實(shí)現(xiàn)输虱。
時(shí)間復(fù)雜度分析與主定理
50.Pow(x, n)
實(shí)現(xiàn) pow(x, n) 些楣，即計(jì)算 x 的 n 次冪函數(shù)(快速冪求法)
class Solution {
public:
double quick_pow(double x,int N)
{
if (N==0) return 1.0;
double y = quick_pow(x,N/2);
return N % 2 == 0 ? y * y : y * y * x;
}
double myPow(double x, int n)
{
int N=n;
return N >= 0? quick_pow(x,N) : 1.0/quick_pow(x,-N);
}
};
x^n = x^(n/2) * x^(n/2) (n為偶數(shù))
x^n = x^(n/2) * x^(n/2) * x （n為奇數(shù)）
n=0時(shí)為邊界，可解
