算法的时间复杂度和空间复杂度分析
实验目的:
通过本次实验，了解算法复杂度的分析方法，掌握递归算法时间复杂度的递推计算过程。
实验环境:
硬件：PC机
软件：windows操作系统，C语言
实验内容：
二路归并排序的算法设计和复杂度分析。
实验过程：
1.算法设计
二路归并算法分为两个阶段，第一个阶段是将待排序列对半拆分，直至拆为全部长度为一的子序列，第二个阶段是将两个相邻的子序列合并为一个有序的子序列，直至把所有子序列合并完全。
第一阶段：
将a1,a2,a3,……,an，由n个元素组成的无序序列拆分，结果为a1，……，a(1+n)/2无序子序列和a(1+n)/2+1.……an子序列。再将以上两个子序列经行递归继续拆分，直到所有子序列长度均为一；
第二阶段：
将拆分为只有单一元素的相邻两个子序列合并并且进行排序。定义一个新的序列，用于存储两个子序列合并后的有序排序结果，作为中转站将排序后的结果返还给完整的序列。
当两个子序列均未被扫描完全时，说明两个子序列中可能依旧存在没有排列好的序列元素，将继续扫描排列，将两序列中第一个元素进行比较，较小的存入tmpa序列中。
当两个子序列其中一个被扫描完全，将剩余的子序列全数录入tmpa序列中。
最后将tmpa序列中的已经排序好的序列存储在最初的序列a中。
流程图如下
2.程序清单
#include<stdio.h>
#include<malloc.h>
void disp(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d", a[i]);
printf(" ");
}
printf("\n");
}
//将两个相邻的有序子序列合并为一个有序子序列
void Merge(int a[], int low, int mid, int high) {
int* tmpa;//tmpa数组用于存放合并后的有序子序列
int i = low, j = mid + 1, k = 0;
tmpa = (int*)malloc((high - low + 1) * sizeof(int));
//两个子序列均未被扫描完时，将子序列的元素复制到tmpa中
while (i <= mid && j <= high) {
if (a[i] <= a[j]) {
tmpa[k] = a[i];
k++;
i++;
}
else {
tmpa[k] = a[j];
j++;
k ++ ;
}
}
//将子序列1剩余的元素全部录入
while (i <= mid) {
tmpa[k] = a[i];
k++;
i++;
}
//将子序列2剩余的元素全部录入
while (j <= high) {
tmpa[k] = a[j];
j++;
k++;
}
for (k = 0, i = low; i <= high;k++,i++) {
a[i] = tmpa[k];
}
free(tmpa);
}
//二路归并算法
void MergeSort(int a[], int low, int high) {
int mid;
if (low < high) {
//将序列拆为长度大致相同的子序列，直至子序列只有一个元素
mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
//将拆分好的两个子序列合并
Merge(a, low, mid, high);
}
}
int main()
{
int n;
int i =0;
printf("请输入你想排列的序列的长度：");
scanf("%d",&n);
int* a = (int*)malloc(n * sizeof(int));
printf("请输入序列中的元素：");
for(i = 0; i < n ; i++){
scanf("%d",&a[i]);
}
printf("排序前：");
disp(a, n);
MergeSort(a,0, n-1);
printf("排序后：");
disp(a, n);
}
3.运行结果
算法复杂度分析
当n=1的时候
T（n）=1
当n>1的时候
T(n)=2T(n/2)+O(n)
=2²T(n/2²)+O(n/2)+O(n)
=2²T(n/2²)+O(n)+O(n)
...
=n*O(1)+(logn-1)*O(n)
=O(n)+(logn-1)*O(n)
=(logn)*O(n)
=O(nlogn)
容易得出 T(n)=O(nlogn)。
故二路归并算法的时间复杂度是O(nlogn)。
实验总结：
本次实验利用自顶向下的方法实现了二路归并排序，通过递归的思想实现了该算法。此算法主要分为两部分，第一部分是将待排序列对半拆分，直至拆为全部长度为一的子序列，第二个部分是将两个相邻的子序列合并为一个有序的子序列，直至把所有子序列合并完全。该算法的时间复杂度是O(nlogn)
