当前课程知识点:Data Structures and Algorithm Design Part I >  01.Introduction I >  B.Computational_Models >  01B-8

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

01B-8在线视频

下一节:01C-1

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

01B-8课程教案、知识点、字幕

我们来看基于RAM模型

实现的一个具体算法实例

这个算法的功能是

在向下取整的意义上的除法

具体来说 对于任何一个非负整数c

和正整数d 我们都需要在做完除法之后

再实施向下取整 得到一个整数

那么这个输出

实际上也就是不超过c/d的那个最大整数

我们可以将它表述为

在所有那些与d相乘以后

不大于c的整数x中的最大值

也可以等效的表述为

在所有乘以d以后严格的小于c+1的

那些整数x中的最大值

这样一种重新的表述

其实不光是文字上的一个转换

更重要的是

它为我们提供了一个对应的算法思路

我们可以将它表述并且实现如下

具体来讲 我们需要保留c+1

并且以它为基础 反复的从中去减除d

因为RAM模型只支持加或者减运算

不断的减除

直到对应的那个寄存器R[0]发生下溢

也就是说 它不再是一个正数

这个时候 我们统计下

在此之前所做过减法运算次数

那么它就是我们所要得到的输出

我们可以将整个这个思路兑现如下

因为这里所有的加法运算和减法运算

都不允许直接对常数进行

而我们一上来就需要做个预处理

对c+1 所有需要利用常数赋值语句

将这个增量1预先的存到一个寄存器

比如R[3]中去

所有接下来我们对R[0]

也就是最初输入的c

加R[3]之后 实际上效果就是c自增

所以在经过这样的预处理之后

c+1确实被存放到R[0]中去了

那么接下来 从第二句开始

如果注意到这里有个goto第2个语句的话

我们就知道这实际上是构成了一个循环

那么这个循环是做什么事呢

正如我们前面所说的那样

它是不断的需要从刚才那个量里头去

刨除掉d

d本身也是作为输入的一部分

已经事先存放在1号寄存器中了

所以每次做的事情

就是从刚才经过预处理以后

存放的实际上是c+1的

那个寄存器R[0]中减除掉d

不断的减除 每减除一次

我们刚才说过

要相应的把计数器累计

这个计数器在哪呢

在我们这里取做的就是R[2]

第2个寄存器 它的初值是0

所以每一次它都要自加

加一个1 而加的这个1

依然是通过我们预先赋值

那个常数存到R[3]中去来实现

经过了这样一次自减

经过了一次计数器的累加之后

我们这个时候就要判断 R[0]

也就是c+1初始的那个数

是否已经不再是一个正数了

如果它还是正数

那就说明还没有减除完

这个时候我们可以通过goto语句

像刚才所说的继续执行这一步

所以反过来说

如果我们有朝一日执行到了第5条语句

那就说明R[0]经过若干次减除以后

已经不再是一个正数

而这个时候呢

我们大致就可以返回这个x

当然 通过精细的分析我们会发现

实际上这个数值是差一的

所以这里头我们还要将R[3]

也就是原来存放的这个常数1

再减一次

经过了这样一次减法以后

再把这个数值返回回去

才会得到真正准确的

我们所需要的那个向下取整的除法值

那么我们把这样的一个

具体实例也罗列出来了

具体来说就是

对于c=12以及d=5来做的一个除法

不难发现 如果不取整的话是2.4

所以向下取整的话 应该得到的是2

不出意外 在我们对照代码

逐行逐条的将整个寄存器序列的内容

作一罗列之后

我们会发现 最终在R[0]这个位置上

会得到并且返回我们

所需要的那个值 也就是2

那么这个算法的正确性

以及更多的例子的给出

留给同学们在课后完成

而我们这里需要向大家

传达的一个重要的概念

是这张表所暗示的

也就是说 我们不光可以把整个计算过程

逐次罗列出来

更重要的是 正像刚才所说的那样

我们将整个计算过程所需要的计算成本

转化为了这个表的规模 或者说它的高度

具体来说就是它的行数

其实就是执行的基本操作的次数

按照我们刚才的推断

实际上就是我们这个算法

所需时间的一个最客观的度量

而这个度量是清晰的 明确的

可比较的 而且没有歧义的

概括一下

我们通过图灵机模型和RAM模型

给大家一个清晰的尺度

这个尺度确实可以用来对算法进行度量

我们可以此判断 哪个算法的性能更好

至少在什么情况下更好

当然 也像我们开篇的时候所说的那样

这只是一把尺子

我们这节只告诉你尺子是什么

那么更重要的一个问题就是

尺子怎么用 如何用好这把尺子

有什么样的一些规则 有哪些技巧

那么我们要留待后续课节再向大家作介绍

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

01B-8笔记与讨论

也许你还感兴趣的课程:

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