分治算法(Divide-and-Conquer)和Google的云计算

发表于:2017-1-22 10:00

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:生命不止    来源:51Testing软件测试网采编

#
Google
分享:
  1.云计算:涉及到存储、计算、资源的调度和权限的管理等
  2.分治算法的原理:
  讲一个复杂的问题,分成若干个简单的子问题进行解决,然后对子问题的记过进行合并,得到原有问题的解
  3.分治算法到云计算
  a.大数组排列的分治算法:
  i.先将大数组一分为2,对每一半进行排序
  ii.对子数组进行合并
  iii.时间复杂度求解:T(N)=2T(N/2)+O(N);其中T(N)为N个元素排列所需的时间,而T(N/2)为N/2个元素的子数组排序所需时间,O(N)为子数组合并的时间,求解的T(N)=O(N*logN),比原来的O(N^2)大大缩短了
  b.矩阵乘法的分治:
  i.对C=A*B分解,将A按行分为n份,B按列分为m份
  ii.C中子集Cn=An*B1,An*B2,...,An*Bm
  Cnm=An*Bm
  最后将Cnm或者Cn汇总即可
  iii.可以用10倍的计算机将计算时间缩短10倍
  c.分治——Map,汇总——Reduce
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号