- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构与算法C语言分治法
学号: 1501010024 姓名:高梁
上机XX 实验名称:分治法
一、逆序对数问题
算法思想
可以使用分治法-归并排序解决上述问题。具体如下:将n个元素分成个数大致相同的两半,且左边的各个元素和右边的各个元素各自有序:
(1)如果左边的元素a[0]右边的元素a[n/2],则逆序对数加1,接着a[0]继续与a[n/2+1]比较,直到碰见a[0]a[n/2+t](tn/2)为止或直到与a[n-1]比较完结束。
(2)接着比较a[1]、a[2]、……、a[n/2-1]与右边的元素,与上述过程相同。
实现代码及运行结果
程序源代码如下:
#include stdio.h
#includestdlib.h
#includemath.h
#define LEN 10
/*********************************归并排序************************************/
//该函数实现,将array[]的左右两半排好序的数组,归并为tmp[],并排序
void Merge(int array[],int tmp[], int start, int mid, int end,int *t)
{
int i = start, j=mid+1, k = start;
while(i!=mid+1 j!=end+1)
{
if(array[i] = array[j])
{
tmp[k++] = array[j++];
*t =*t+mid-i+1;
}
else
tmp[k++] = array[i++];
}
while(i != mid+1)
tmp[k++] = array[i++];
while(j != end+1)
tmp[k++] = array[j++];
for(i=start; i=end; i++)
array[i] = tmp[i];
}
//递归的调用此函数,实现折半划分,只完成划分,不实现排序,最终返回array[]数组有序
void MergeSort(int array[], int tmp[], int start, int end,int *t)
{
int midIndex;
if(start end)
{
midIndex = (start + end) / 2;
MergeSort(array, tmp, start, midIndex, t);
MergeSort(array, tmp, midIndex+1, end, t);
Merge(array, tmp, start, midIndex, end, t);
}
}
/****************************mian函数*************************************/
int main()
{
int a[LEN]={4,1,9,8,5,6,7,3,10,2},b[LEN],t=0;
for (int i=0;iLEN;i++)
printf(%4d ,a[i]);
printf(\n);
MergeSort(a, b, 0, LEN-1,t);
printf(逆序对数为:%d\n,t);
return 0;
}
实验结果:
当数组a[LEN]={4,1,9,8,5,6,7,3,10,2}时,程序运行结果见下图,达到预期结果。
当查找元素a[LEN]={4,1,9,8,5,6,7}时,程序运行结果见下图,达到预期结果。
复杂度分析及算法改进
(1)时间复杂度
算法中,每一次查找将有哪些信誉好的足球投注网站范围缩小为原来的一般,即将一个规模为n的问题变成一个规模为n/2的问题,每次归并需要移动n次,即时间复杂度为O(n)。因此,该算法的时间复杂度T(n)可表示如下:
T(n)= T(n/2)+O(n)
可得T(n)=O(nlogn)。
(2)空间复杂度
算法中使用b[LEN]个临时空间(用于存储数组a[LEN]的排序数),因此空间复杂度S(n)=O(n)。
算法改进
可以考虑使用三分查找(或K分查找),不知道效率是否会更好。
二、大整数乘法问题
算法思想
A和B的乘积AxB。如果把A分解成A=a*10^
文档评论(0)