本文主要是介绍高级算法设计与分析 学习笔记1 递归与分治法 复杂度计算 大数乘法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本章的目录：
排序问题的示例与分析：递归与分治
插入排序：
类似于排序扑克牌。先把第一个元素当成已排序序列，然后把第二个纳入，用一次插入排序，然后将第三个纳入……
插入排序性能分析
大O表示上界，最差情况不外如是。
欧米噶表示下限，最好情况。
这里的上界下界一般都是确界，是刚刚好的情况，不是随便选一个特别大或者特别小的情况就可以。
中间有一杠的O，表示其上界下界都可以用一个级别的函数表示（只有系数差距，没有质变）
小o表示上界是f(n)，且下界不是f(n)
对付大批量数据，还是要用分治法：
我们可以简单发现归并排序复杂度是log2n级别的。但是如果这个表达式是更加复杂的版本呢？
复杂度计算法：
方法一：猜一个式子，然后用数学归纳法验证它。
先假设在0<n<n0的时候T(n)<=cn^3，把式子带进去。
可以看到只要c随便取一个比2大的数，就可以轻松秒杀任意的n0，绝杀无解。不过n^3有点太大了吧？
cn^2+n绝无可能比cn^2小，没办法了吗？好像差距不大啊：
这里再举一个例子：
下面这种算法是
递归树法：
先写上可以确定的作为最上层的，叶子就是还不确定，要接着算的，然后就接着拆开……
主方法
注意这种方法专门针对这种形式，是这种问题的简单解法。
这样求解公式被分成了两个部分。
如果f(n)比较小（真小的那种，不能是相当，而且是n^某某次方（不是无穷小，/lgn啥的不行））那就就是以n^logb(a)为主
如果二者相当，那就是n^logb(a) * lg(n)
如果f(n)比较大且占据n^*级别优势，那就是f(n)为主。这个条件比较苛刻，还要求af(n/b) <= cf(n) (c要小于1！，n要大)
注意这里的都是带等号的O！上下界都是这个，是很强的结论
我们举几个例子：
最后一个例子中，虽然是f(n)比较小，应该是第一种情况，但小得不够多，不构成n^*级别优势，所以不成。
三种方法中，最后这种主方法是最重要的。
大整数乘法
XY的乘法式子可以改写成两种形式：
改写成下面两种形式只需要3次乘法（原版要4次）实际上一般用1方法，先做减法比较好。
这篇关于高级算法设计与分析 学习笔记1 递归与分治法 复杂度计算 大数乘法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
