算法与数据结构(二)嵌套与俄罗斯套娃
嵌套与俄罗斯套娃
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.
相关推荐
shenwenjie 2020-09-24
xiesheng 2020-08-02
mingyunxiaohai 2020-07-28
Cypress 2020-07-08
Cypress 2020-06-28
Dyancsdn 2020-06-27
Masimaro 2020-06-21
waitwolf 2020-06-21
Jasmineyaoyao 2020-06-16
OldBowl 2020-06-16
alicelmx 2020-06-16
Masimaro 2020-06-14
waitwolf 2020-06-08
nurvnurv 2020-06-05
ustbfym 2020-06-04
ziruoxiangyi 2020-06-03
范范 2020-06-03
Jasmineyaoyao 2020-05-31