当前课程知识点:Data Structures and Algorithm Design Part I >  02.Vector II >  F.Mergesort >  02F-5

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

02F-5在线视频

下一节:02F-6

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

02F-5课程教案、知识点、字幕

为了更好地理解 刚才那个算法的过程

我们不妨分几种情况 来给出具体的图示

同样 这是整个的_elem数据区

这是待归并的

两个子序列的公共的部分

以及最终要归并的内容

在算法的过程中

我们分别用i j k来指示

这三个子向量中的

当前我们所关注的那个元素

我们首先来考虑第一种情况

也就是 i还是介于lo和mi之间

没有越过mi这个界线

还没有进入到

C这个子向量的范围

这种情况 我们讲是很自然的

因为显然i不可能居于j的左侧

顶多是个平齐

所以每次迭代中

如果需要发生数据转移的话

无论是B[j]转移到A[i]

还是C[k]转移到A[i]

我们可以看出来 整个数据

从内容来讲 都不会发生覆盖

是安全的

功能上讲 也是正确的

再来看相对复杂一点的情况(b)

也就是当这个i在持续增加之后

终于有一天 会越过mi

进入C的区域

表面看 这样会侵犯到C的区域

但是我们说 实际上不要紧

因为在这个时候

k绝对不会位于i的左侧

所以 介于mi和i之间的这些元素

其实作为C中原来的元素

必然已经归入到A中

当然是它的左侧

在i之前的这部分中的

某一个适当的位置中去了

所以这种情况 表面看有点危险

但是我们说 依然是安全的

无论是C[k]、还是B[j]转移到A[i]中去

都不会导致C中已有的元素

被无意中覆盖掉

从而导致错误

我们再来看最后两种

更为复杂的情况

也就是 我们刚才所说的

有可能在某个时候

B这个子向量已经提前耗尽

具体来说 就是它其中的元素

已经完全地归入到A中

当然也是就位了

而在C中还残存有部分的元素

没有转移和就位

我们说 这种情况下

正如我们刚才所说的

我们的逻辑其实相当于等效地

是在B的最右侧

就是lb这个位置上

增加了一个哨兵节点

而且它的数值就是正无穷

因此即便C的右侧 还残存有若干个元素

它们也会在接下来的各次迭代中

因为是与这样一个正无穷相比

而被认为是更小

从而顺利地转移到A中适当的位置

直到两个子向量都同时耗尽

那么反过来 另一种对称的情况就是

C也可能会提前耗尽

同样正如我们此前所分析的那样

我们这里所给的逻辑

也相当于等效地 在C的最右侧

增加了一个数值为正无穷的哨兵

它的秩是lc

如果真发生这种情况的话

即便在B的尾部 还残存有部分的元素

我们说 也不要紧

它们也等效于

和这样一个数值为正无穷的哨兵相比

或者说 它们总是会被认为是更小

所以按照算法的逻辑

会等效地转移到A中

剩余的对应区域中去

整个这个过程也是会顺利地进行

不会出现我们所说的数据遗漏

或者数据被无意中覆盖

细心的同学可能已经注意到了

(c)和(d)这两种情况其实并不对等

因为按照我们这里的设计

其实向量C和B 地位本来就是不等的

B是完全复制出来的一个缓冲部分

而C虽然是独立的绘制出来

但实际上它就在A中 占据右端

换而言之 如果是C提前耗尽

我们确实需要把B尾部的这些元素

悉数转移到A的尾部

但如果是B提前耗尽

那么对C尾部这些元素的转移

其实都是多余的

因为它们原来就在那

完全没有必要

注意到这样一个现象的话

我们就不难对刚才表面上很规范的逻辑

进一步的精简

也就是说将我们这里所有的灰色部分

都给它抹去

这个括号 这个括号以右

以及这个逻辑

当然也包括这对括号

还有这个逻辑和这个逻辑

那么这里最最重要的其实就是这个部分

就像我们刚才所说的

我们并不需要考虑C提前耗尽的那种情况

我们只需要考虑B提前耗尽的那种情况

一旦B提前耗尽

我们就可以直接终止这个循环包括这个算法

所以这样的话

可以使这个算法效率进一步的提高

尽管不是从渐进角度而言的一种实质的提高

那么这个算法在原来

以及包括这样精简之后

从渐进意义上讲 复杂度是多少呢?

是否能像我们最初所预期的那样

能够有大幅度的提高呢?

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

02F-5笔记与讨论

也许你还感兴趣的课程:

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