01E-5慕课视频播放-Data Structures and Algorithm Design Part I-MOOC慕课视频教程-柠檬大学

我们再来看

减而治之策略的另一个

典型的应用实例

这个问题要求对于

任何给定的数组

将其中元素的存放位置

前后颠倒

就像翻烙饼一样

这里我们给出一个统一的接口

以便不同的算法

能够在统一的接口下实现

也就是将数组A中

从lo一直到hi

大家注意包括lo,包括hi

这样的一个区间中的所有的元素

实现刚才所说的前后颠倒

当然有很多种算法

我们这里

不妨给出其中的一种

我们来看一下

我们不断地来判断一下

如果lo和hi之间

还有足够多的元素

还没有到退化的情况

我们就将当前的lo和当前的hi

这两个元素彼此互换

接下来呢

递归地去求解一个

规模更小的问题

这个问题从数组的范围来说

是从lo + 1到hi - 1

为什么它是减而治之呢？

因为我们可以认为

通过这样一次O（1）时间的操作

可以将问题规模减少为

（比）原来规模少2个元素

那么当然

这里其实隐含着有一个else

你可以认为这个else后面

直接给了一个return

没有做任何的事情

但是它确实隐含在这儿

而这个隐含的return呢

实际上就是我们所说的递归基

所以大家这里要回去验证一下

对于这个问题而言

我们的递归基是不是

足以应付所有的情况

我给大家的提示

这里实际上有两种情况要解决

哪两种呢？

取决于这个区间的宽度

我们知道区间的宽度

经过了这样的一个减而治之以后

虽然有所减少

但每次减少的都是两个单位

所以它的奇偶性是不变的

最终的情况

实际上有最小的奇数

1个元素以及最小的偶数

也就是0个元素的两种情况

请大家回去验证一下

不可见的这个else

都是足以应付的

好我们再回到这个算法的本身

它是一个减而治之的一个策略

它的正确性我们也可以用

这样一个图来表示

再看一遍

为了求解这样一个

将n个元素前后颠倒次序的问题

我们将它转化为一个

平凡的问题

也就是将这一对元素lo和hi互换

以及另一个规模缩小

在这里讲具体是两个单位的问题

但是这个问题的形式

和原来那个问题的形式

是完全一样的

所以它可以继续递归得以实现

当然这个问题还有别的版本

比如说有迭代版

甚至还有更精简的迭代版

这个呢我们留给大家

课后进行推敲

我们把注意力还是放在

这个递归的算法

我们要问一问

这样一个也能够证明

是正确的算法

它的复杂度相对于

最初的问题的规模n

也就是lo和hi的差

具体的是多少？

我们请大家参照上述所给的

两种主要的方法

针对这样一个减而治之策略的算法

来分析它的时间复杂度

并且相互佐证

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

01E-5在线视频

01E-5课程教案、知识点、字幕

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

01.Introduction I

01.Introduction II

02.Vector I

02.Vector II

03.List

04.Stack+Queue

05.Binary_Tree

06.Graph

01E-5笔记与讨论

也许你还感兴趣的课程: