《Algorithms》第2章：Divide-and-conquer algorithms 学习笔记
1、

2、高斯发现两个复数乘法初看涉及4次实数乘法运算，但实际上可以简化为3次乘法运算。例：(a+bi)(c+di) = ac - bd + (bc+ad)i ，其中bc+ad = (a+b)(c+d) - ac - bd所以只需计算(a+b)(c+d) 、 ac 和 bd。
这条原理可以帮助我们实现更好的乘法运算，将n位的x、y分成n/2位长，于是：
运行时间：T(n) = 3T(n/2) + O(n), 解得时间复杂度为n^1.59， 比n^2效率更高。

3、依据以下定理可迅速写出时间复杂度。

4、分治策略的典型应用：二分搜索和归并排序。二分搜索：T(n) = T(n/2) + O(1) ==> O(logn)归并排序：T(n) = 2T(n/2) + O(n) ==> O(nlogn)

归并排序代码（C&#43;&#43;）：<br><br>7、矩阵乘法：可以分解成7个n/2规模的子矩阵乘法，所以T(n) = 7T(n/2) &#43; O(n^2), 解得O(n^2.81)<br><br><br><br><br><br><br><br><br><br><br> </p></div><div style="margin:0 auto;width:300px;height:250px;position:relative;"> <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script> <!-- 移动端全站正文 --> <ins class="adsbygoogle" style="display:block" data-ad-client="ca-pub-6147101717324856" data-ad-slot="1958144088" data-ad-format="auto"></ins> <script> (adsbygoogle = window.adsbygoogle || []).push({}); </script></div> <div class="subn-nav"><a href="//m.reader8.net">读书人网</a> ><a href="//m.reader8.net/jiaocheng/biancheng/">编程</a></div><div class="sp-jctu"><h3><span> 热点推荐 </span></h3><ul><li><p><a href="//m.reader8.net/jiaocheng/20150822/2672277.html">JAVA基础-java中ET的差异</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140726/2508209.html">ByteBuffer跟String的互相转换</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140726/2508208.html">vim 编辑器的三种模式怎么切换</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140725/2505463.html">电脑编码</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140725/2505462.html">地图reduce编程模型介绍</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140724/2502708.html">Java基础java缓存读写资料小例子</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140724/2502707.html">学习jar下令 创建和解压jar文件包</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140723/2499938.html">java生成随机数、四舍五入、当前时间的</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140723/2499937.html">[猖獗Java讲义精粹] 第十一章|多线程</a></p></li> <li><p><a href="//m.reader8.net/jiaocheng/20140722/2497120.html">Java Thread 小结</a></p></li> </ul></div><div style="display:none;"> <script> var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "//hm.baidu.com/hm.js?d6151f323a57d16696165e47eee86d53"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); </script></div> <div class="footer"><p>触屏版 | <a href="//www.reader8.net/jiaocheng/20120730/1966095.html#fromapp">电脑版</a></p><p>读书人网 m.reader8.net</p></div> <script language="javascript"> function clickme(sad){ var divobjdiv = document.getElementById("divobjdiv" + sad); if(divobjdiv.style.display =="none"){ divobjdiv.style.display ="block"; }else{ divobjdiv.style.display ="none"; } var wenzi = document.getElementById('divobjimg' + sad); if(wenzi.innerText == "收起"){ wenzi.innerText = "查看更多"; }else{ wenzi.innerText = "收起"; } } </script> <div id="back-top"><a href="#top"><span></span></a></div> </body> </html>