蓝色经典通用网站模板,个人网站找谁建设好,单仁牛商,长沙哪里学网站建设数据结构----算法–分治,快速幂
一.分治
1.分治的概念
分治法#xff1a;分而治之
将一个问题拆解成若干个解决方式完全相同的问题
满足分治的四个条件
1.问题难度随着数据规模缩小而降低
2.问题可拆分
3.子问题间相互独立
4.子问题的解可合并
2.二分查找(折半搜索)…数据结构----算法–分治,快速幂
一.分治
1.分治的概念
分治法分而治之
将一个问题拆解成若干个解决方式完全相同的问题
满足分治的四个条件
1.问题难度随着数据规模缩小而降低
2.问题可拆分
3.子问题间相互独立
4.子问题的解可合并
2.二分查找(折半搜索) BinaryChop
前提有序
时间复杂度O(log2的n次方)
1.循环实现二分查找
//循环
int BinaryChop1(int a[], int begin, int end ,int find) {if (a nullptr || begin end) return -1;while (begin end) {int mid begin(end- begin)/2 ;if (a[mid] find) {cout 找到了,返回在数组中的下标 endl;return mid;}else if (a[mid] find) {begin mid 1;}else if (a[mid] find) {end mid - 1;}}return -1;
}2.递归实现二分查找
//递归
int BinaryChop2(int a[], int begin, int end, int find) {if (a nullptr || begin end) return -1;int mid begin(end- begin)/2;if (a[mid] find) {cout 找到了返回数组下标 endl;return mid;}else if (a[mid] find) {begin mid 1;}else if (a[mid] find) {end mid - 1;}return BinaryChop2(a, begin, end, find);}二.快速幂
求一个数的幂次方
例如2的50次方
//简单写法这种写法求一个数的幂次方速度慢
int a2;
for(int i0;i50;i){a*a;
}//快速幂写法
int x2
int n50;
int ans1;
while(n){tempn1;if(temp){ans*x;}x*x;nn1;
}
printf(%d,ans);快速幂就是将幂数二进制化
然后和1位与如果得1 最终要输出的结果就乘以当前位的数否则不乘
之后将幂数左移一位当前位的数自乘
重复进行操作直到幂数为0结束
看一道具体的题网址https://leetcode.cn/problems/powx-n/
题目实现 pow(x, n) 即计算 x 的整数 n 次幂函数即x的n次方 。
代码如下
//这里的代码是c语言下的
class Solution {
public:double myPow(double x, int n) {int Bool0;int Bool20;int tx;if(n0x!0){return 1;}if(x0){return 0;}double ans1;int temp0;if(n0){if(n-2147483648){n2147483647;Bool21;}else{nabs(n);}Bool1;}while(n){tempn1;if(temp){ans*x;}x*x;nn1;}if(Bool2){ans*t;}if(Bool){ans1.0/ans;}return ans;}
};
