递归

如何设计一个高效的DSA呢？ 分而治之

不要一下解决 要分解问题成子问题 慢慢解决

举一个很简单的例子

时间复杂度是O(n)  其实只需要看循环结构  没有循环的地方复杂度肯定是O(1)

空间复杂度的两种想法

1、输入的A[] n 还有sum i

空间复杂度是O(n)

2、输入的A[] n 不计入  

只有sum i

我们更倾向于第二种

也就是这个算法的空间复杂度是O(1)

通常来讲 

凡是空间复杂度的讨论都是

除了输入本身所占的空间之外

我们所需要的另加的用于计算所必须的空间

上述例子给了我们一个处理问题的方法

处理问题的方法：

这个平凡 指的是这个问题很容易解决了

缩减 指的是问题的规模小了 但是类型没变 

因此可以一直这么处理下去  直到该大问题全部解决

递归算法分析的第一个技巧 递归跟踪

递归跟踪：

查看复杂度的时候  递归中调用自己的那个归入下一层递归中 这一步的复杂度是O(1)不影响大局

当前递归只关心A[n-1]这一步

可以看到的是每一步的sum(A,n)时间复杂度都是O(1)因为只有个加法

一共有n+1次递归  那么一共就有O(1)*（n+1）=O(n)

上述的递归是一个前递归产生一个后递归  也叫线性递归

为了更好的分析复杂的递归

我们给出另外一种方法 递推方程

间接抽象,更适用于复杂的递归模式

如果递归

上述是隐式表达 由递推方程和边界条件就能解出显式表达

另外一个例子：

另一个策略 分而治之

所谓的递归基 就是最简单的情况  最容易解决的情况

就像下面的区间变成一个元素 区间上限下限相等

 这就是递归基

直到lo全部等于hi的时候才行

查看刚才的递归 

把递归调用本身去掉的话

没有循环 也不包含任何隐式显式迭代

所以要计算时间复杂度的话我们只需要把递归的个数算出来就行了

那么问题来了  ：怎么算

从代数层面看 是列代数方程式

但是 我们不想 或者说 不喜欢你采用这种方式

我们从几何层面看

每一层都是2的倍数对吧 

关键是最后一层是多少

最后一层是n 没错 为什么呢  因为最后一行等价于把每个元素罗列出来

最后一个元素其实就是n  但是为了写成 等比数列的形式呃。。。也就是以2为倍数的几何级数的形式

几何级数的形式 时间复杂度与末项同阶

再从递归方程的角度分析

MAX2问题 

首先第一个方法

最好和最坏情况比较次数都一样都是2n-3

第二个方法  扫描一遍逐个比较

这个方法的好处在于  最好情况确实减少了时间 但是最坏情况并没有改善

以上两种情况都是只看了if语句  没有关心里面的时间复杂度 或者说默认了swap这个函数的复杂度是O(1)

以上算法的最坏情况没有真正改进  接下来给出真正意义上的改进算法

首先把整个数组划为两部分  然后分别求出这两部分的最大值和次大值

X1L与X1R先比较  X1L胜出的话  X1L为整体最大值

X2L再和X1R比较  确定整体次大值

注意 这里X2R是不需要比较的

注意代码语法 应该是使用了引用的那个语法 &x1直接在函数里修改X1L X1R X2L X2R

自己写一写试试吧