leetcode之分治递归
2020-09-09 本文已影响0人
FakeCSer爱去网吧
思想与特性
分治（分而治之），分治法将原问题划分为若干规模较小且结构与原问题相同或相似的子问题，分别解决子问题，最后合并其问题的解，即可得到原问题的解。
- 子问题应当是相互独立，没有交叉的。
- 分治到一定小规模的子问题可解
- 分治常用递归实现，也可以非递归实现。
时间复杂度分析与主定理
50.Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数(快速幂求法)
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为偶数)
x^n = x^(n/2) * x^(n/2) * x （n为奇数）
n=0时为边界，可解
