当前课程知识点:Data Structures and Algorithm Design Part I >  01.Introduction II >  D.Algorithm_analysis >  01D-5

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

01D-5在线视频

下一节:01D-6

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

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

我们的第一个问题 关乎这个算法的有穷性

也就是说这个算法 是否必然会终止

答案首先基于这个算法所具有的这样一条不变性

可以断言 上述这个算法

在经过了K轮的外循环

也就是 K轮的扫描交换之后

全局最大的那K个元素 必然会各就各位

来看一下下面这个图

如果由上而下是构成整个这个序列

也是我们整个扫描交换的执行方向

那么 在第一趟扫描过程中

5和2 因为逆序会交换次序变成2和5

再接下来 5当遇到7以后 会停留下来

因为在这个位置是构成了一个顺序对

那么接下来的情况将是7

一旦接过这样一个控制权以后

它作为全局最大的元素

必然会在接下来的每次比较中

都大于它当时的右侧

也就是 后边的那个元素

从而 构成一个逆序紧邻对

所以 7会和接下来的邻居4

以及再接下来的新邻居6

以及再接下来的邻居3 以至1

统而言之 它的所有的后继依次交换

最终效果是7 经过若干次交换

转移至最后 而原来它的那些后继

等效于 往前平移一位

我们看到刚才这个断言

对于第一趟是对的

因为经过了K等于1 一轮的扫描交换

最大的一个元素 也就是7

确实是就位了

这不奇怪

因为7是整体的最大的元素

所以 在扫描交换的过程中

一旦它接过控制权

后面的故事都是一样的

它会胜出所有的元素 直到最终就位

那我们看看 在接下来的第二轮循环之后

又会怎么样呢?

其实故事是类似的

也就是说 在这里2和5是顺序的

所以不用交换

但是5和4经过一次交换以后 变成4和5

这都不是最关键的

我们看 最关键的是

一直这个故事发生到

当前最大的元素

也就是 全局第二大的那个元素6

接过控制权之后

它会跟刚才一样

胜出它的所有的有效的那些后继

在这个例子讲的3和1

直到它也就位

所以推而广之

后面接下来最大的元素5

也会在接下来的一轮扫描交换之后就位

同样4、3和2都会相继的就位

因此总结一下 这条不变性确实是成立的

另外呢 在这整个过程中

也蕴含了一个单调性

经过了K轮的扫描交换之后

问题的实质的等效规模

实际上就会减至n-k

在我们这个图里 已经用颜色加以了标识

所有的彩色的部分 都对应是

当前这个算法有效的问题范围

也就是说 我们还没有处理的范围

而灰色的部分都可以认为是

整个这个算法 当前的视线之外

对于算法后续的过程

以及整体的算法的效果

没有影响的部分

我们看到 如果最开始的规模是n的话

经过了一趟以后 确实缩减为n减1

再经过一趟以后 缩减为n减2

以致n减3、n减4 n减5 一直下去

所以由这两条 我们就应该可以得出结论

这个算法必然会结束

而且是正确的结束

而且在终止的时候呢

我们来考察一下这个不变性

也就是它的最后的那个边界情况

当k等于n的时候

那么 不变性就可以翻译成

经过了 n轮扫描交换之后

最大的n个元素

其实 也就是所有的n个元素

必然会各就各位

最后归纳一下 确实

这个算法经过至多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

01D-5笔记与讨论

也许你还感兴趣的课程:

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