实验一算法的时间复杂度和空间复杂度分析

比眉伴天荒 2022-12-17 14:59 193阅读 0赞

### 目录 ###

*  实验目的:
 *  实验环境:
 *  实验内容：
 *  实验学时：
 *  实验过程：
 *   *  1.算法设计
     *  2.程序清单
     *  3.运行结果
     *  4.算法复杂度分析
 *  实验总结：

# 实验目的: #

通过本次实验，了解算法复杂度的分析方法，掌握递归算法时间复杂度的递推计算过程。

# 实验环境: #

硬件：PC机  
软件：windows操作系统，C语言

# 实验内容： #

二路归并排序的算法设计和复杂度分析。

# 实验学时： #

# 实验过程： #

## 1.算法设计 ##

我们采用分治的算法将一个序列分成两个大概相等的小部分，对小部分重复调用该函数，使小部分完成排序，最后再合并两个小部分，完成排序。

## 2.程序清单 ##

#include<stdio.h>
    void margin(int a[],int b[],int l1,int r1,int l2,int r2){ 
    	int p=l1;
    	int begin=l1;
    	while(l1<=r1&&l2<=r2){ 
    		if(a[l1]<=a[l2]){ 
    			b[p]=a[l1];
    			l1++;
    			p++;
    		}else{ 
    			b[p]=a[l2];
    			l2++;
    			p++;
    		}
    	}
    	while(l1<=r1){ 
    		b[p]=a[l1];
    		l1++;
    		p++;
    	}
    	while(l2<=r2){ 
    		b[p]=a[l2];
    		l2++;
    		p++;
    	}
    	for(int i=begin;i<=r2;i++){ 
    		a[i]=b[i];
    	}
    }
    void sort(int a[],int b[],int begin,int end){ 
    	if(begin==end)return ;
    	else { 
    		int mid=(begin+end)/2;
    		sort(a,b,begin,mid);
    		sort(a,b,mid+1,end);
    		margin(a,b,begin,mid,mid+1,end);
    	}
    }
    
    int main(){ 
    	int b[8],a[8];
    	int i;
    	for(i=0;i<8;i++){ 
    		a[i]=8-i;
    	}
    	sort(a,b,0,7);
    	for(i=0;i<8;i++){ 
    		printf("%d ",a[i]);
    	}
    	return 0;
    }

## 3.运行结果 ##

1~8逆序变正序，运行正确

## 4.算法复杂度分析 ##

采用分治递归的思路解决，时间复杂度O(nlogn),  
T(n)=2*T(n/2)+n;  
T(n)=4*T(n/4)+2*n;  
T(n)=n*T(1)+n\*log2n;  
所以时间复杂度为O(nlogn),

# 实验总结： #

C++中，数组指针都以地址的方式进行传输，不需要返回值即可对参数完成修改，今后要多多使用C++，使自己更加熟悉C++语言特性。