算法学习3

1.递归行为时间复杂度

需要使用master公式：
T(N) = a * T(N / b) + O(N ^d)
a：表示在递归函数中递归函数被使用的次数
b：表示每个递归函数计算个数占整体多少份的倒数
O(N ^d)：表示在整个递归函数中除去调用函数的其他代码的时间复杂度

如：
递归函数的代码

int process(int[] arr,int L,int R){
if(L == R)
return arr[L];
int mid = L + ((R - L) >> 1);
int leftMax = process(arr,L,mid);
int rightMax = process(arr,mid + 1,R);
return Math.max(leftMax,rightMax);
}

其master公式为：
T(N) = 2 * T (N / 2) + O(1)

时间的复杂度：

1. 当log_ba < d 时，其时间复杂度为O(N^d)
2. log_ba = d 时，其时间复杂度为O(N^log(b,a))
3. log_ba > d 时，其时间复杂度为O(N^d * logN)

2.归并排序

原理：
将数组分为左右两部分，分别对左右两部分进行排序；
从左右部分的第一个数进行比较大小，将大（或者小）的数拷贝到一个辅助数组的第一个位置；
取左右部分中已经拷贝的元素的下一位数，与另外部分未拷贝的元素接着比较，并拷贝到辅助数组中，直到左右部分中的其中一部分全部拷贝过一遍；
接着将左右部分中未完全拷贝的部分，按照其当前顺序全部拷贝到辅助数组中；

其代码如下：

//分别将左右部分进行排序
public void process(int[] arr,int L,int R){
if(L == R)
return arr[L];
int mid = L + ((R - L) >> 1);
int leftMax = process(arr,L,mid);
int rightMax = process(arr,mid + 1,R);
merge(arr,L,mid,R);
}

//将整体进行排序
public void merge(int[] arr,int L,int M,int R){
int[] help = new int[R - L + 1];
int i = 0;
//p1为左边部分的下标，p2为右边部分的下标
int p1 = L;
int p2 = M + 1

//对左右下标的元素进行比较，并将合适的数拷贝到辅助数组中
while(p1 <= M && p2 <= R){
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}

//还没有拷贝的部分进行拷贝
while(p1 <= M){
help[i++] = arr[p1++];
}
while(p2 <= R){
help[i++] = arr[p2++];
}

for(i = 0;i < help.length;i++){
arr[L + 1] = help[i];
}
}

原文地址：https://blog.csdn.net/qq_65818377/article/details/142442591

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！