《Algorithms》第2章：Divide-and-conquer algorithms 学习札记

《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++）：<br><br>7、矩阵乘法：可以分解成7个n/2规模的子矩阵乘法，所以T(n) = 7T(n/2) + O(n^2), 解得O(n^2.81)<br><br><br><br><br><br><br><br><br><br><br> </p><div class="aged2"><script type="text/javascript">a("article_content_down");</script></div> </div> <div id="pagebox" > <a href="/jiaocheng/biancheng/" target="_blank">查看更多</a> <A href="/jiaocheng/20121122/1966092.html" title="private承继与复合">下一篇</A></div> <div id="MainLeftll"> <div id="MainLeftllToolbar">本文网址：<a href="https://www.reader8.net/jiaocheng/20120730/1966095.html">https://www.reader8.net/jiaocheng/20120730/1966095.html</a></div> <div class="related"><span class="relatedIco1">读书人精选</span> <ul class="relatedList"> </ul> </div> <div class="aged3"><script type="text/javascript">a("article_content_down2");</script></div> <div class="aged3a"><script type="text/javascript">a("article_content_down3");</script></div> </div> </div> <!-- 文章正文左边结束 --> <!-- 文章正文右边开始 --> <div class="leftbox_r"> <div class="aged4"><script type="text/javascript">a("article_right_up");</script></div> <div class="Rtitle"> <span class="Rtitle_text">热点排行</span></div> <div class="RContl"> <ul> <li><a href="/jiaocheng/20140123/1912529.html" target="_blank">maven 项目平添Maven Dependencies Libr</a></li> <li><a href="/jiaocheng/20140122/1943016.html" target="_blank">java类静态域、块，非静态域、块，结构函</a></li> <li><a href="/jiaocheng/20140125/1973610.html" target="_blank">Golang的slice圈套</a></li> <li><a href="/jiaocheng/20140715/2477185.html" target="_blank">Spring2 兑现AOP编程的两种实现方法</a></li> <li><a href="/jiaocheng/20140705/2451858.html" target="_blank">树的底层实现（下）</a></li> <li><a href="/jiaocheng/20140424/2313132.html" target="_blank">多线程程序的评量基准</a></li> <li><a href="/jiaocheng/20140721/2494264.html" target="_blank">struts2札记之第七讲</a></li> <li><a href="/jiaocheng/20140709/2460644.html" target="_blank">jquery 用ID取某个元素上的某个ID元素</a></li> <li><a href="/jiaocheng/20120620/1952160.html" target="_blank">Lisp语言：函数的可选参数，剩下参数以及</a></li> <li><a href="/jiaocheng/20120829/1859533.html" target="_blank">thinking in java 学习札记10内部类</a></li> </ul> </div> <div class="aged7"><script type="text/javascript">a("article_right_up2");</script></div> <!-- 文章正文右边结束 --> </div> <!--主体结束--> <script type="text/javascript">a("article_down_up");</script> <script type="text/javascript">a("foot");</script> <script type="text/javascript">a("article_down_up2");</script> <!--主体结束--> <div style="display:none"> <!--百度统计代码--> <script> var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?d6151f323a57d16696165e47eee86d53"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); </script> </div> <script type="text/javascript">a("allbt");</script> </body> </html>