网站大量收购独家精品文档,联系QQ:2885784924

数据结构与算法C语言分治法.doc

  1. 1、本文档共9页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 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)

juhui05 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档