当前课程知识点:Data Structures and Algorithm Design Part I >  01.Introduction II >  F.Dynamic_Programming >  01XC-9

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

01XC-9在线视频

下一节:01XC-A

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

01XC-9课程教案、知识点、字幕

这个算法的正确性

是可以得到保证的

准确地讲 是由于它所具有的

某种单调性

这种单调性 可以理解为

在这个算法中 每经过一次递归

无论减而治之 还是分而治之

我们只需要经过一次比对

原问题的规模 总是可以减小

确切地讲

每经过一次比对操作之后

新生成出来的递归实例

所对应的一对序列中

至少有一个的长度

会相对于此前 缩短一个单位

比如说 在最好的情况下

会始终只出现减而治之

而不会出现分而治之的情况

在这种情况下

每一个递归实例

都会缩减为一个

而不是两个递归实例

而且它所对应的

两个序列的长度

都会单调地减少一个单位

所以相应地 这样下去

至多经过这两个序列的

长度总和这么多时间

算法必然就会终止

这个结果非常好

因为这意味着 在这种情况下

我们只需要线性规模的时间

然而 一旦有第二种情况

也就是 分而治之出现

就不那么简单了

因为在这种情况下

原来的那个问题

将会被分解为两个

而不是一个子问题

更糟糕的是呢

这两个子问题的规模之和

居然大致是原来那个问题的两倍

而且在进一步导出的子问题中

也有类似的情况

从而造成总体上 大量的雷同

这种现象 与我们此前所讲的

Fibonacci数的那个递归算法 完全类似

我们可以把刚才那个

表格的局部展开

放大来看一下

为什么会出现这种情况

在这个表格中 任何一个单元

都对应一个递归实例

每一个递归实例

都分别对应于一对序列

每一次 我们都会去比较

它们的末字符

比如说 这里的是LG

这里的是AG 包括这个是LA

如果它们确实是相同的

比如说 这里的情况

刚才我们讲过

它会减而治之地

降解为一个新的问题

这个问题相当于

把原来的这两个序列

相同的末字符都抹掉

我们刚才说 这是好的情况

但是更一般的情况是 不等

比如这里的情况

在这个时候 每一个递归实例

都会转化为两个递归实例

就像我们刚才所说的

这两个递归实例

不仅在数量上增加了

而且总的规模

几乎是原来的两倍

更糟糕的是 它们还会继续地

引发雷同的递归实例

比如 还是这个例子

由这个递归实例会引发

这样两个递归实例

而我们这两个递归实例

都会进而唤醒

这个公共的递归实例

这就是我们所说的雷同

这种重复度是远远超乎

我们的直观想象的

为了就此做一估算

我们不妨从更宏观的角度

来重新审视

刚才我们所制作的这张表格

不妨把其中所有的递归实例

分别按坐标的形式

也就是它们所对应的

那一对序列的长度

表示为n m或者是a b

当然包括最初的0 0

那么我们来问一个问题

为了计算出 最终这个递归实例

也就是n m所对应的解

我们需要唤醒其中

某一个特定的递归实例

也就是a b多少次呢?

其实不难理解

根据这样的行走的方向

我们说最坏的情况下

所唤醒的次数应该等于

介于这两个隔点之间的

所有通路的数目

这样的路径每一条

就对应于a b 被唤醒一次

反之亦然

因此运用一下组合数学

就可以得出

为了计算出最终的这个结果

我们唤醒a b

这个递归实例的次数

应该是等于在它们之间

所有合法通路的总数

也就是n-a 再加上m-b中

去挑选出n-a条

水平路径的总数

这样的方案数

或者等效地

在刚才那么多段路径中

挑选出互补的

m-b条垂直的路径的总数

这个总数是多少呢?

我们不妨取其中的一个特例

也就是0 0来做估算

这个时候a b分别等于0和0

所以这个总数其实也就是总体

这个表格的行和宽的总和

也就是m+n中 去挑选出n

或者等效地挑选出m

如果这个表格是接近

甚至是完全是方形的话

这个总数大致就是2的n次方

没错 我们这里

又再次地碰到了指数

又掉进了指数复杂度的悬坑

下面我们就来看看

如何跳过这个悬坑

Data Structures and Algorithm Design Part I课程列表:

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--(a)计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-(xd):LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

01XC-9笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。