算法与数据结构(二)嵌套与俄罗斯套娃

嵌套与俄罗斯套娃

算法与数据结构(二)嵌套与俄罗斯套娃

 

1 什么是嵌套算法:

•        每次有不同的输入

•        但是每次运算相同

•        必须有停止嵌套的条件(防止死循环)

•        与循环的不同:每次输入数据范围缩小

2 为什么要用嵌套算法:

•        能用嵌套不用循环:好写 好读
•        问题可以分解为相同的小问题(处理的数据范围变小)
•        广泛应用于 树, 图 数据结构中
•        广泛应用于三种问题:
•        分而治之 – Divide and conquer
•        贪婪算法 -  Greedy
•        动态编程 – Dynamic programing

3. 怎么分析理解运行结果

理论上是通过LIFO 的 stack 缓存实现:把套娃一个一个拆开先放好(输入数据集的大小就是套娃的大小, 数据集拆分的次数就是套娃的个数),从最小一个套娃开始再一个一个的合上。

题目一:从有序list里面查找一个值,返回index

实现代码如下:

  算法与数据结构(二)嵌套与俄罗斯套娃

 

解析:
嵌套方法数据集排列
  
要找的数据是3, 所以实际套娃个数是3就够了
如果找的数据是5,那么套娃个数是4
输出结果

算法与数据结构(二)嵌套与俄罗斯套娃

当查询数据是5时,输出结果如下: 

例子2:求n的阶乘

分析:数据集的变化 n*(n-1) (n > 1)
如果n=5 那么 结果为 5*(4*(3*(2*(1)))),代码如下:

例子3:

斐波纳契数列(一种整数数列)前两个数是 0,1 后面数字是前面个数字的和。
0,1,1,2,3,5,8…
分析:f(n) = f(n-1) + f(n-2)

算法与数据结构(二)嵌套与俄罗斯套娃

嵌套算法的特点

•        嵌套可以用循环实现
•        Space  -- 需要使用stack 空间

什么时候用嵌套

•        问题可以分为本质一样的小问题
•        对时间和空间要求不高
•        需要一个快速的解决方案的时候 – 实现简单

嵌套的应用

•        Stack
•        Tree
•        Sorting: quick sort, merge sort
•        Divide and Conquer
•        Dynamic programing etc.

相关推荐