算法第二章总结

将要求解的较大规模的问题分割成k个更小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。 分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。

缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

用主定理求解型为T(n)=aT(n/b)+O(nd)的递归方程

设a>=1和b>1是常数,f(n)是一个函数,T(n)是定义在非负整数集上的函数:T(n)=aT(n/b)+ O(nd)

算法第二章总结

 

 

 

               

 

上一篇:tensorflow2.0——部分采样


下一篇:Python数据分析(3)-numpy中nd数组的创建