计算机科学导论-计算思维程序实践 课件汇 L06 冯·诺依曼计算机-L16 信息安全与网络空间安全

第6讲冯.诺伊曼计算机

-机器程序及其执行学习目标本章目标：掌握冯.诺依曼计算机的相关概念理解机器指令、机器程序，以及机器程序在存储器中的存储理解机器执行机构理解机器执行程序的过程本章内容：理解冯

诺依曼计算机的贯通性思维，即关于机器指令、机器级算法和机器程序及其存储和执行的相关联思维。第六章冯.诺依曼计算机——机器程序及其执行一、机器级算法与机器程序二、存储器及机器程序与数据的存储三、CPU-运算器和控制器：机器程序执行机构四、一台完整的计算机五、计算机架构六、国内典型的微处理器计算机器的基本功能第一讲机器级算法与机器程序计算机器按计算规则(程序)对输入（数据）进行变换，得到输出（数据）。输入计算规则(程序&指令)输入/输出都是0和1的形式表达输出计算规则也是0和1的形式表达数据数据程序计算机器的核心运算器中央处理单元CPU控制器存储器(主存或内存)程序数据程序与数据的保存程序执行与数据计算微处理器(芯片)可能包含多个CPU（即多核，m个控制器n个运算器）第一讲机器级算法与机器程序计算机如何计算一个运算式?8

32+23+6第一讲机器级算法与机器程序计算方法：Step1:取出数3至运算器中Step2:乘以数8在运算器中Step3:加上数2在运算器中Step4:乘以数3在运算器中Step5:加上数6在运算器中计算方法：Step1：取出数3至运算器中Step2：乘以数3在运算器中Step3：乘以数8在运算器中Step4：存结果

在存储器中Step5：取出数2至运算器中Step6：乘以数3在运算器中Step7：加上在运算器中Step8：加上数6在运算器中算法---机器可执行的求解问题的规则及步骤。机器级算法问：怎么看待算法节省的步数?---算法需要“优化”第一讲机器级算法与机器程序【机器指令】是CPU可以直接分析并执行的指令，一般由0和1的编码表示。机器指令指令

操作码+地址码；0000010000000111操作码地址码(如取数，加法等操作)(操作中的数据的来源)000100

0000000100000010

0000000100000011

0000001010000100

0000001010机器语言—机器能够执行的所有指令的集合。第一讲机器级算法与机器程序机器程序：将机器级算法用机器指令进行表达假设数字3、8、2、6分别存储在8号、9号、10号和11号存储单元机器级算法机器语言与机器指令机器程序00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000第一讲机器级算法与机器程序计算机器是按计算规则对输入数据进行变换得到输出数据的机器。机器级算法是指一组有先后次序的计算步骤。机器指令是一种编码。（操作码和地址码）机器程序是用机器可以直接执行的指令所编写的程序。通过机器指令将机器级算法转换为机器程序。小结第六章冯.诺依曼计算机——机器程序是如何被执行的一、机器级算法与机器程序二、存储器及机器程序与数据的存储三、CPU-运算器和控制器：机器程序执行机构四、一台完整的计算机五、计算机架构六、国内典型的微处理器什么是存储器？【存储器】:能够按地址读或写每一个存储单元的部件。【存储单元】：一个存储单位可以保存一个m位的数据，通常记为Dm-1…D0。【地址】：是一个n位的0/1编码，每一个编码指向一个存储单元，通常记为An-1…A0。第二讲存储器及机器程序与数据的存储存储器的性能指标——存储容量存储单元(的内容)(存储单元的)地址地址空间存储字长存储容量地址编码n位：An-1…A0地址空间：

00000000…0000000000000000…00000001……11111111…11111111存储字长m位：存储位的位数，Dm-1…D0

每个存储单元都是m位存储容量：存储器所能存储的二进制代码的总位数

=2n

mBit(位)=2n

m/8Byte（字节)存储容量的单位：210为换算单位2n个存储单元DB、NB、BB、YB、ZB、EB、PB、TB、GB、MB、KB、Byte第二讲存储器及机器程序与数据的存储第二讲存储器及机器程序与数据的存储存储器的性能指标——存储速度存取时间：读出时间和写入时间存储器周期：存储器进行连续读写操作所需的最短间隔时间存储器带宽：存储器连续访问时，提供的最大的数据传输率启动存取存取完毕下次存取存取时间附加时间存储器周期计算8

32+2

3+6的程序机器程序存储器存储单元000001000000100000010000000010010000110000001010000100000000100000001100000010110000100000001100000101000000110000011000000000000000000000000011000000000000100000000000000000100000000000000110

地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000程序数据将机器程序和数据装载进存储器中?第二讲存储器及机器程序与数据的存储程序与数据以同等地位存于存储器中你能读懂这段程序吗？第二讲存储器及机器程序与数据的存储换一种写法——你能读懂吗?第二讲存储器及机器程序与数据的存储改改机器程序，体验机器程序计算8

32+2

3+6的程序计算5

42+3

4+7的程序计算ax2+bx+c的程序?

机器程序存储器存储单元00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000程序数据00000000000001000000000000000101000000000000001100000000000001110000000000000011000000000000100000000000000000100000000000000110第二讲存储器及机器程序与数据的存储读一读程序，能发现什么吗？程序指令系统第二讲存储器及机器程序与数据的存储0001110000001010取出8号存储单元的数至运算器中（数0000010000001000，十进制为1032）加上9号存储单元的数（数0000110000001001，十进制为3081）得到3081+1032，即4113在运算器中加上10号存储单元的数（数0000110000001010，十进制为3082）得到4113+3082，即7195在运算器中将结果存入10号存储单元中。（7195的二进制0001110000001010，存入0000000000001010（10号）存储单元）跳转到10号单元的指令继续执行（10号单元存储的是什么）存储单元中的内容可能是指令，也可能是数据，还可能既是数据又是指令存储器中的程序是可能被修改的，即初始时是执行预期的程序，而再执行可能就不是当用跳转指令改变程序执行次序时，要注意其指向的是否是指令？可能会出现错误小结存储器：一种能读出、写入、保存0和1数据的部件。存储单元、存储字长。存储器的性能指标：存储容量和存储速度机器程序在存储器中的存储第六章冯.诺依曼计算机——机器程序是如何被执行的一、机器级算法与机器程序二、存储器及机器程序与数据的存储三、CPU-运算器和控制器：机器程序执行机构四、一台完整的计算机五、计算机架构六、国内典型的微处理器(数据)寄存器算术逻辑部件R0=R1

R0(赋值,R0既是一个操作数，又保存运算结果)。其中为算术、逻辑及移位运算符(数据)寄存器0000000000001000000000000000100100000000000000000000000000000000算术、逻辑及移位运算R0R1运算器第三讲CPU-运算器和控制器：机器程序执行机构运算器为什么要如此设计呢？减少寄存器的数目，缩短指令长度时钟与节拍发生器信号控制PCIR算术、逻辑及移位运算R0R1(数据)寄存器程序计数器PC指令寄存器信号控制器——发出控制信号时钟与信号发生器——控制操作次序注：PC：程序计数器---存储下一条要执行指令的地址IR：指令寄存器---存储当前指令内容运算器控制器控制器第三讲CPU-运算器和控制器：机器程序执行机构PC自动加1，保证程序按顺序执行。小结运算器是对数据实现算术、逻辑和移位运算的部件。算术逻辑部件，数据寄存器；R0=R1

R0控制器是可以读取指令、解释指令并调用各个部件执行指令的部件。PC、IR、信号控制部件、时钟与节拍发生器第六章冯.诺依曼计算机——机器程序是如何被执行的一、机器级算法与机器程序二、存储器及机器程序与数据的存储三、CPU-运算器和控制器：机器程序执行机构四、一台完整的计算机五、计算机架构六、国内典型的微处理器运算器寄存器算术逻辑部件控制器程序计数器PC指令寄存器信号控制器时钟与节拍发生器存储器存储单元地址存储单元内容计算机各部件内部的简单构成关系第四讲一台完整的计算机第四讲一台完整的计算机总线：各部件通过一组线路，以适当的接口电路，与外围设备连接，这组共用的连接线路被称为总线。片内总线：芯片内部的总线。系统总线：CPU、内存、输入输出设备之间的信息传输线。局部总线：连接某一子系统或部分部件的总线。通信总线（外部总线）：计算机之间或计算机与其他机器之间传送信息的总线总线的分类第四讲一台完整的计算机典型指令的执行需要哪些信号？“读取指令”的信号分解：（a）将PC中的地址发送给存储器。（b）给存储器发送一个开始工作的控制信号。（c）存储器按地址读取相应存储单元的内容。（d）给拟接收改内容的指令寄存器IR发送接收的控制信号(a)(b)(c)(d)第四讲一台完整的计算机典型指令的执行需要哪些信号？“取数指令”的信号分解：（a）给IR发送一个控制信号，将指令中的地址码发送给存储器。（b）给存储器发送一个开始工作的控制信号。（c）存储器按地址读取相应存储单元的内容。（d）给拟接收改内容的数据寄存器发送接收的控制信号(a)(b)(c)(d)0000010000001001典型指令的执行需要哪些信号？“加法指令”的信号分解：

(a)(b)(c)(d)0000110000001001(e)(f)第四讲一台完整的计算机不同的指令，由一组不同的电信号构成。最小的时间区隔单位--时钟周期。不同的时钟周期状态称为节拍。多个节拍构成一个机器周期，一条指令占用一个或多个机器周期。同一指令的电信号在时钟与节拍的控制下按次序产生传输。指令执行问：机器的“主频”指的是什么?时钟周期、节拍与机器周期第四讲一台完整的计算机时钟与节拍发生器信号控制0000000000000000

PCIR

算术、逻辑及移位运算

地址内容R0R1(数据)寄存器程序&指令数据运算器控制器存储器初始状态第四讲一台完整的计算机——以一条指令模拟执行过程时钟与节拍发生器信号控制寄存器00000000000000000000010000001000--(随机的数值)--(随机的数值)--(随机的数值)--(随机的数值)算术、逻辑及移位运算00000100000010000000000000000000地址内容

R0R1PCIR运算器控制器存储器第1条指令：取指令（2个节拍）第四讲一台完整的计算机——以一条指令模拟执行过程0000010000001000时钟与节拍发生器信号控制寄存器00000000000000010000010000001000--(随机的数值)0000000000000011--(随机的数值)--(随机的数值)算术、逻辑及移位运算00000000000000110000000000001000地址内容

控制R0R0R1000001PCIR--(随机的数值)0000000000000000运算器控制器存储器第1条指令：执行指令（2个节拍）第四讲一台完整的计算机——以一条指令模拟执行过程时钟与节拍发生器信号控制寄存器00000000000000010000010000001000--(随机的数值)0000000000000011--(随机的数值)--(随机的数值)算术、逻辑及移位运算00000000000000110000000000001000地址内容R0R1PCIR运算器控制器存储器第1条指令执行结束状态第四讲一台完整的计算机——以一条指令模拟执行过程时钟与节拍发生器信号控制寄存器00000000000000010001000000001001--(随机的数值)0000000000000011--(随机的数值)--(随机的数值)算术、逻辑及移位运算00010000000010010000000000000001地址内容

R0R1PCIR0000010000001000运算器控制器存储器0000000000000011第2条指令：取指令（2个节拍）第四讲一台完整的计算机——以一条指令模拟执行过程时钟与节拍发生器信号控制寄存器0000000000000010000100000000100100000000000010000000000000000011--(随机的数值)--(随机的数值)R0算术、逻辑及移位运算R100000000000010000000000000001001地址内容

控制R1

000100PCIR--(随机的数值)0000000000000001运算器控制器存储器0000010000001001第2条指令：执行指令（4个节拍）第四讲一台完整的计算机——以一条指令模拟执行过程时钟与节拍发生器信号控制寄存器0000000000000010000100000000100100000000000010000000000000011000--(随机的数值)--(随机的数值)R0算术、逻辑及移位运算R100000000000010000000000000001001地址内容

000100PCIR0000000000000011运算器控制器存储器机器级程序的执行过程模拟(5)第2条指令的执行第2条指令：执行指令（4个节拍-续）第四讲一台完整的计算机——以一条指令模拟执行过程小结总线分为系统总线、片内总线和通信总线（外部总线），现代计算机还引入了局部总线。指令由一组电信号构成，指令执行是在时钟与节拍控制下传输和接收信号的过程。以一条指令模拟了机器执行过程。第六章冯.诺依曼计算机——机器程序是如何被执行的一、机器级算法与机器程序二、存储器及机器程序与数据的存储三、CPU-运算器和控制器：机器程序执行机构四、一台完整的计算机五、计算机架构六、国内典型的微处理器数据流控制流冯.诺依曼体系结构：由存储器、运算器、控制器、输入设备和输出设备组成。以运算器为中心的冯.诺依曼体系结构第五讲计算机架构冯.诺依曼体系结构——缺点：

所有的操作都要经过运算器

当输入输出占用运算器时，运算器就不能计算，当运算器计算时，就不能输入输出以存储器为中心的现代通用计算机体系结构第五讲计算机架构第五讲计算机架构非冯.诺依曼体系结构第五讲计算机架构非冯.诺依曼体系结构——达芬奇架构计算单元：用于人工智能运算，例如矩阵计算；存储系统：由片上存储单元和相应的数据通路构成；控制单元：为整个计算过程提供指令控制。主要包括系统控制模块，标量指令处理队列，指令发射模块，矩阵运算队列，向量运算队列，存储转换队列和事件同步模块等。第五讲计算机架构微处理器架构RISC一种具有较少类型计算机指令的微处理器，其核心思想精简指令集。CISC一种指令系统比较丰富的微处理器。不仅包含了一些常用的指令，还有专用指令。Intelx86Intel研发的一种微处理器体系结构的泛称。在台式计算机上应用更广泛。ARM是一个32位精简指令集处理器架构，使用在许多嵌入式系统设计中。MIPS是一种流水式处理指令的微处理器架构，使用在许多电子产品、网络设备等。RISC-V基于RISC原理建立的开放指令集架构，具有完全开源、设计简单等优点。晶体管的数目还是继续按照摩尔定律在推进；单核微处理器：是指一个微处理器只有一个CPU。多核微处理器：是指在一个微处理器中封装有多个CPU，可以并行处理。片上系统（SoC）：是一个有专用目标的集成电路，它包含完整系统并有嵌入软件的全部内容。第五讲计算机架构微处理器发展史小结冯.诺依曼体系结构，现代通用计算机体系结构，非冯诺依曼体系结构（达芬奇架构）；微处理器架构；单核、多核、片上系统。第六章冯.诺依曼计算机——机器程序是如何被执行的一、机器级算法与机器程序二、存储器及机器程序与数据的存储三、CPU-运算器和控制器：机器程序执行机构四、一台完整的计算机五、计算机架构六、国内典型的微处理器认识华为鲲鹏处理器7nm制程，数据中心ARM架构处理器鲲鹏916鲲鹏920支持多路互联的ARM架构处理器

CPU个数：32核，2.4GHz主频计算性能：SPECint性能匹配业界中端，功耗低至75W内存连接：支持4通道DDR4控制器外存连接：支持PCI-e3.0和SAS/SATA3.0网络连接：集成板载GE/10GE网络处理器连接：支持2路互联CPU个数：计算核数提升1倍，最多64核计算性能：SPECint性能提升超过2倍内存连接：内存通道数提升1倍，支持8通道DDR4控制器外存连接：支持PCI-e4.0和CCIX网络连接：集成板载100GE网络和加密、压缩加速引擎处理器连接：支持2路或4路互联ARM是一种CPU架构，采用RISC精简指令集（ReducedInstructionSetcomputer），是一种开放的快速发展中的CPU架构。有别于Intel、AMDCPU采用的CISC复杂指令集(ComplexInstructionSetComputer)，第六讲国内典型的微处理器华为鲲鹏处理器的构成Chip：是指将几块硅片封装后形成的芯片，如鲲鹏916、鲲鹏920。通常情况下Chip是一种SoC（Systemonchip）即芯片中除了CPU外，还集成了网卡、磁盘控制器和I/O控制器等。DIE：芯片的最小物理单元。鲲鹏920封装了3个DIE（也可以封装2个DIE，可选择），两个用来做计算，第三个用来做I/O。Cluster：若干个核(core)的集合。鲲鹏920把4个core集合成为一个cluster，而一个DIE上有8个cluster。Core：真正的计算单元，CPU或称为“核”。ClusterCoreDIECPUDieCPUDieI/O

DieChip第六讲国内典型的微处理器ringLLCLLCLLCLLCLLCLLCLLCLLCSLLCARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DARMCoreL1IL2L1DringLLCLLCLLCLLCCluster-1Cluster-2CPUDieTaiShanCore独享L1Cache和L2Cache，4个Core和1个L3Cachetag组成一个Cluster，6~8个Cluster组成一个CPUDie，合封后的两个CPUDie共享LLC(LastLevelCache)。华为鲲鹏处理器的多核与多级CacheCache：高速缓冲存储器，是位于CPU和主存储器之间规模较小但速度很高的一种存储器L1I:L1级指令Cache;L1D:L1级数据Cache;L2:L2级Cache;LLC:L3级Cache.第六讲国内典型的微处理器L2L2L2…L2L2L2L3L2L2L2…L2L2L2L3L3…L3L2L2L2…L2L2L2RemoteL3RemoteL3…HomeL3L2L3MainMemory（2）PrivateCache：有N个Private的L3，每个PrivateL3只缓存对应的L2的数据。即一个进程(程序)只能使用对应的部分L3的容量，无法使用全部L3的容量，L3和L3之间不通信（1）ShareCache：对所有的L2来说L3cache是共享的，一个进程(程序)可以使用整个L3的容量（3）PartitionedCache：与Private相同的是，一个进程(程序)只能使用对应的部分L3容量；与Private不同的是，L3细分为一个Home的L3和N个Remote的L3，Home的L3类似L4，所以L3和L3之间会通信，由Home的L3来维护多个PartitionedL3之间的一致性（4）Non-inclusiveL3：非包含性L3,即Memory和L2间直接数据访问华为鲲鹏处理器的多级Cache的不同使用方式第六讲国内典型的微处理器Kunpeng920SAS控制器桥片CPURoCE网卡Kunpeng920Kunpeng920HCCSHCCSHCCSHCCSKunpeng920Kunpeng920多合一SoCxPU高速互联注：HCCS(HuaweiCacheCoherenceSystem)华为自研片间互联协议高集成高能效单位功耗的SPECint性能更高5.03Kunpeng920-48核Kunpeng920-32核Others3.634.5230%每1万台Hadoop节点每年节电

1千万度碳排放每年减少

1万多吨华为鲲鹏处理器的特色：高集成高能效第六讲国内典型的微处理器认识华为昇腾处理器第六讲国内典型的微处理器华为昇腾处理器组成芯片系统控制CPU:包括任务调度器、AICPU和控制CPU，集成了8个ARMA55，还有一个专用CPU作为任务调度器(TaskScheduler,TS)。AICore:昇腾AI芯片的计算核心,负责执行矩阵、向量、标量计算密集的算子任务，采用达芬奇架构。昇腾310和910处理器分别集成了2和32/20个AICore。多层级的SoC缓存或缓冲区：SoC片内有层次化的memory结构，Alcore内部有两级memorybuffer，SoC片上还有8MBL2buffer。DVPP：数字视觉预处理子系统，完成图像视频的编解码，用于将从网络或终端设备获得的视觉数据进行预处理以实现格式和精度转换等要求，之后提供给AI计算引擎。第六讲国内典型的微处理器认识飞腾处理器主频：2-2.2GHZ内核数：64核核心架构：FTC663二级缓存：32MB三级缓存：64MBTDP功耗：136W腾云S2500腾锐D2000主频：2.0-2.6GHZ内核数：8核核心架构：FTC663二级缓存：8MB三级缓存：4MBTDP功耗：25W第六讲国内典型的微处理器飞腾处理器腾锐D2000架构集成8个FTC663核，2个DDR4-3200控制器，支持对DDR存储数据进行实时加密;集成34个LanesPCIe3.0接口，2个X16(每个可拆分成2个X8)和2个X1;集成2个千兆Ethernet接口(RGMII)，支持10/100/1000Mbps自适应;集成1个SD卡控制器，兼容SD2.0规范;集成1个HDA(HD-Audio)，支持音频输出，可同时支持最多4个Codec;集成对称、非对称和杂散密码加速引擎;集成4个UART，1个LPCMaster，32个GPIO，4个I2C，1个QSPI，2个通用SPI，3个CAN，2个WDT;第六讲国内典型的微处理器内容总结机器级算法，机器指令及机器程序；存储器构成，机器程序在存储器中的存储；运算器，控制器；总线，指令信号的执行次序，以一条指令模拟机器程序的执行过程；计算机体系结构：冯.诺依曼体系结构，非冯.诺依曼体系结构国内典型的微处理器：华为鲲鹏，华为昇腾，飞腾D20001第10章

算法：程序与计算系统之灵魂2本章导图3本章学习什么--理解算法类问题求解框架4一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择序列求和问题求解为例5算法---计算机与软件的灵魂。最早的算法：公元前3世纪，欧几里得《几何原本》，求最大公约数的辗转相除法算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。如音乐乐谱、太极拳谱等都可看作广义的算法什么是算法？6数字序列求和问题算法Input: n个具有先后次序的数字序列D={d1,d2,...,dn}；Output:

序列D的n个数字之和；Step1.

令一个变量sum的值为0，令一个变量i的值为1；Step2.将Di累加到sum，并将i增加1；Step3.

若i小于等于n转到Step2；否则输出sum，算法结束。算法的5个基本特征n

有穷性：一个算法在执行有穷步规则之后必须结束。n

确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。n

输入：算法有零个或多个的输入。n

输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。n

能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成)，并能在有限时间内完成。7一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择序列求和问题求解为例8u单位执行时间：执行一次基本运算所需的平均时间，用来做基本单位u时间复杂度:

如果一个问题的规模是n，求解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，则T(n)称为这一算法的“时间复杂度”。ü基本参数

n——问题规模，表明输入数据的规模大小ü把复杂性或运行时间表达为n的函数。算法获得结果需要多长时间?时间复杂度算法的时间复杂度l 时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。l 算法的时间复杂度与计算机的性能无关l 时间复杂度是衡量算法本身求解问题效率的一种度量标准。9时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。

此处是线性增长趋势。时间复杂度分析示例算法10.1数字序列求和问题Input: n个具有先后次序的数字序列D[1...n]；Output:

序列D的n个数字之和；Step1.

令一个变量sum的值为0，令一个变量i的值为1；Step2.

将Di累加到sum，并将i增加1；Step3.

若i小于等于n转到Step2；否则输出sum，算法结束。Step1：2条赋值语句；Step2：2条加法语句（重复n次）；Step3：执行1条判断语句（重复n次），算法结束前，执行1条输出语句T(n)=2+2n+n+1=

3n+310u“大O记法”：渐进时间复杂度n越大，低阶项和系数的影响越小去掉低阶项和系数，再用O进行标记“O”表示量级

(order)，允许使用“=”代替“≈”，如3n2+4n+1

=Ο(n2)。O(f(n))渐进时间复杂度与大O记法算法10.1数字序列求和问题Input: n个具有先后次序的数字序列D[1...n]；Output: 序列D的n个数字之和；Step1.

令一个变量sum的值为0，令一个变量i的值为1；Step2.

将Di累加到sum，并将i增加1；Step3.

若i小于等于n转到Step2；否则输出sum，算法结束。T(n)=3n+3=

O(n)11指数量级：O(bn),

O(n!)多项式量级：O(1),O(log

n),O(n),O(n

log

n),O(nb)不同的时间复杂度量级以1百万个单位时间为1秒时间复杂度问题规模nn=10n=100n=1000O(1)常数0.001毫秒0.001毫秒0.001毫秒O(logn)对数0.003毫秒0.006毫秒0.0096毫秒O(n)线性0.01毫秒0.1毫秒1毫秒O(nlogn)线性对数0.03毫秒0.66毫秒9.97毫秒O(n2)平方0.1毫秒10毫秒1秒O(2n)指数1毫秒4*1016年3.4*10287年O(n!)阶乘3.6秒2.9*10144年1.3*102555年12一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例13数学建模是用数学语言描述实际现象的过程，即建立数学模型的过程。数学模型是对实际问题的一种数学表述，是对部分现实世界为某种目的而进行的一个抽象与简化的数学结构。算法类问题求解的第一步就是数学建模【示例】攀岩问题：小明在训练攀岩，下图记录了每分钟上升或下降的高度，共14分钟的数据，定义“连续时间上升高度”为某个时间点t1到另一个时间点t2之间上升与下降的数据总和，例如第7~10分钟内的上升高度为7+7-5+7=16，要求找出最大的“连续时间上升高度”。这个问题怎么求解呢?14攀岩问题：抽象成“最大子序列和问题”,

序列：一组具有先后顺序的整数。最优化问题：在给定的约束条件下,

求解最优的方案使得目标最大化或最小化的问题。这个问题是最优化问题。不同时间上升/下降高度--

整数序列连续时间上升高度--

子序列和将社会/自然问题

转化为

数学问题【示例】最大子序列和问题：已知一个数字序列，在其中找到一个连续的子序列，使得该子序列之和是所有的子序列和中的最大值。15最大子序列和问题的数学模型数学模型的四个核心要素：l 输入l 输出l 约束l 目标通过自然数及其下标将不同的数据关联起来，是算法类问题抽象的重要方法。16任何子序列可由di,di+1,...,dj表达，其中i和j分别为子序列的起点和终点。数学模型，可发现问题求解的基本思路任何子序列之和可用“数字序列求和算法”求出。所有可能的i和j的组合（1≤i≤j≤n）穷举了所有可能的子序列。所有可能的子序列之和的最大值是问题的解。穷举/遍历17一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例18(数据的)逻辑结构(数据的)存储结构操作反映逻辑语义关系为什么需要数据结构数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。u数据的逻辑结构描述数据之间的逻辑语意关系；u数据的存储结构是在反映数据逻辑关系的原则下，便于计算系统处理的物理结构为便于计算系统处理19数据的逻辑结构与存储结构用线性表描述攀岩问题用树描述家族谱系用图描述校园地图常见逻辑结构：线性表、树、图。线性表：n（n≥0）个具有相同特性的数据节点构成的有限序列树：一种逻辑上表现为一颗倒挂的树的结构图：一种由节点和连接节点的边构成的结构20线性表及其操作接口u线性表（Linear

List）是一种由n（n≥0）个具有相同特性的数据节点构成的有限序列，可以记为a1,a2...an，除了首尾元素，线性表中的每个元素都有一个直接前驱和一个直接后继，第一个元素只有直接后继，最后一个元素只有直接前驱。u数据结构的目的是为算法提供数据操纵机制，这种操纵机制由数据结构的操作接口提供，表现形式为一批定义良好的函数集，这些函数集合构成了数据结构可供外部使用的操作接口。l IS-EMPTY(L)

如果线性表L的长度为0，则返回1，否则返回0；l LENGTH(L)

获得线性表L中元素的个数；l L[i]或GET(L,

i)

获取线性表L中的第i个元素（1≤i≤n）；l PRIOR(L,

i)

获取线性表L第i个元素的前驱元素（2≤i≤n）；l NEXT(L,

i)

获取线性表L第i个元素的后继元素（1≤i≤n-1）；l L[i]←x或UPDATE(L,

i,

x)

将线性表L的第i个元素改为x；l INSERT(L,

i,

x)

在线性表L的位置i处插入元素x，原位置i及其后面的的元素都向后移动一个位置；l DELETE(L,

i)

从线性表L中删除位置i处的元素，原位置i+1及其后面的的元素都向前移动一个位置。线性表的操作接口21u用顺序表存储数据时，元素在内存中是连续的。u顺序表的元素在逻辑上的排列顺序和物理上是一致的，若i<j，元素aj在逻辑上和物理上都在ai之后。线性表的存储结构之一：顺序表22u

链表的每个元素除了存储数据，还有一个指针保存了下一个元素的地址（称为next指针）。u元素在内存中的位置不是连续的，访问元素时，只能从第一个元素开始，沿着next指针依次访问下一个元素

。线性表的存储结构之二：链表23u顺序表的元素存取效率很高，因为顺序表支持随机存取。u

随机存取：通过元素的逻辑地址直接计算元素的物理地址以便进行存取。u顺序表的存储操作所需时间与问题规模n无关。顺序表和链表在存取操作上的差异顺序表中元素的物理地址计算公式：元素的物理地址=顺序表开始物理地址+(元素逻辑地址-1)*元素占用字节数访问顺序表元素的时间复杂度：O(1)u链表的元素存储效率较低，因为链表仅支持顺序存取。u

顺序存取：给定逻辑地址i，只能先依次访问第1、2...i-1个元素，才能访问第i个元素。u链表的存取操作所需时间与问题规模n相关，n越大，访问后面的元素所需时间越长。链表中的元素地址无法直接计算，只能顺着链表元素去访问访问链表元素的时间复杂度：O(n)24u顺序表要保持物理存储位置上的连续性。u删除第i个元素后，必须将第i+1到第n个元素向前移动一个位置（通过内存拷贝操作），以填补因删除第i个元素而留下的空位。顺序表和链表在删除操作上的差异删除顺序表元素的时间复杂度：O(n)u链表的元素在物理存储上不要求是连续的。u链表删除第i个元素后，将第i-1个元素的next指针改为第i+1个元素的地址。删除链表元素的时间复杂度：O(1)25为最大子序列和问题选择合适的数据结构线性表与问题的输入高度吻合用顺序表的效率更高（1）以数学模型为基础，确定数据的组织结构；（2）根据组织结构选择一种合适的逻辑结构；（3）确定需要对数据进行哪些操作；（4）根据这些操作从备选的存储结构中选择一种能高效支持这些操作的存储结构。u问题的输入：

n个具有先后次序的数字组成的序列D={d1,d2,...,dn}

。u线性表：由n（n≥0）个具有相同特性的数据节点构成的有限序列。数据结构设计的方法。26一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例27ü分支结构：“如果Q成立，那么执行A，否则执行B”

，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则或语句的一种结构

。ü循环结构：控制规则或语句多次执行的一种结构---迭代(iteration)u循环结构又分为有界循环结构和条件循环结构。ü有界循环：

“重复N次执行A”，其中N是一个整数。ü条件循环：某些时候称为无界循环，“重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。算法与程序的基本控制结构算法的控制结构描述了算法的操作步骤，控制结构的设计反映了算法的思想ü顺序结构：“执行A，然后执行B”，是按顺序执行一条条规则或语句的一种结构

。28流程图的基本表示符号ü矩形框：表示一组顺序执行的规则或者程序语句。ü菱形框：表示条件判断，并根据判断结果执行不同的分支。ü圆形框：表示算法或程序的开始或结束。ü箭头线：表示算法或程序的走向。算法的程序流程图表达方法描述算法的方法：自然语言描述法、流程图、伪代码29三种控制结构的流程图表达开始第1条规则或语句第n条规则或语句结束顺序结构的流程图算法的程序流程图表达方法开始条件成立否？是否条件成立时执行的规则或语句结束条件不成立时执行的规则或语句分支结构的流程图循环结构的流程图初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句。即：循环体结束是否循环结束30u可能解：解的取值空间中任何可能的一个值

。可能解与解空间最大子序列和问题的可能解：任意符合1≤i≤j≤n的i和j都形成一个可能解.例: D[2...6]、D[3...9]都是问题的可能解。u解空间：由问题的所有可能解构成的集合

。最大子序列和问题的解空间：所有可能的i和j的组合构成的子序列的集合。解空间大小:

Cn2=

n(n+1)/2问题求解的过程：在解空间中搜索符合问题约束以及优化目标的解。最基本的算法：遍历-计算-验证（穷举法）。31穷举法求最大子序列和问题的流程图穷举法：对问题的解空间进行遍历，对遍历中的每个可能解进行逐一验证，若某个可能解符合问题的约束条件和优化目标，则为该问题的最终解。【示例】最大子序列和问题的穷举法思想u

将任意可能解表达为D[i...j]，1≤i≤j≤n；将思想/策略u

将i设计为外层循环结构的循环变量，j为内层循

转变为“步骤”环结构的循环变量；u

在内循环中，用算法10.1求子序列D[i...j]之和；u

时间复杂度：O(n3)。不同数据结构设计给算法带来不同的性能；若使用链表存储序列D，算法时间复杂度将变为O(n4)。32算法的伪代码表达方法u伪代码：一种介于计算机语言和自然语言之间的语言，主要目的是以精确、简洁、易于理解的方式描述算法。u

比自然语言描述法更为精确，比流程图更简洁，更容易用程序设计语言实现。伪代码符号33穷举法求最大子序列和问题的伪代码算法10.2

最大子序列和问题的穷举算法Input:

大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和functionFIND-MAX-SUBSEQ-2(D[1...n])beginres←-∞;

//初值为负无穷大for

i←1tondo//i为子序列起点7 for

j←itondo//j为子序列终点8sum←0for

k←i

to

j

do

//子序列求和910sum←sum+D[k]endforres←MAX(res,sum)//MAX返回较大值endforendfor输出res16end

beginu计算学科的学生不仅能够设计算法，而且会描述和表达算法，更要能读懂算法。u最外层循环：枚举子序列起点。

u中间的循环：枚举子序列终点。u最内层循环：计算子序列之和。时间复杂度为：T(n)=

O(n3)34穷举法优缺点及其一般步骤u穷举法优点：思路简单易于实现，只要分析清楚如何遍历解空间，计算可能解，然后验证可能解，即可设计出相应的算法

。u穷举法缺点：因为需要遍历所有的可能解，若解空间很庞大，效率会很低

。设计穷举法的一般步骤（1）建立问题的数学模型，需要明确四要素：输入、输出、约束、优化目标；（2）以数学模型为基础，选择合适的数据结构，数据结构要便于控制结构的操作；（3）以数学模型为基础，分析问题的解空间形式；（4）设计控制结构对解空间进行遍历，对于每个可能解，使用数学模型中的约束和优化目标进行验证以便找到符合要求的解；35一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择优化思想之一：“累加和”相减36算法优化的基本方法是消除无效计算消除无效计算的三种手段：u消除不必要遍历：利用问题的约束条件来控制遍历的范围，停止对非必要部分的遍历。u消除重复计算：在遍历解空间的过程中，检查不同可能解的验证是否存在重复的计算，如果存在，则暂存已验证可能解的结果，将之用于另一个可能解的验证；u优化解空间搜索策略：不使用穷举法这种直接遍历解空间的控制结构，而是利用一些行之有效的算法策略，设计更高效的解空间搜索策略。学习算法的过程：学习如何在众多算法策略中选择适合特定问题求解的策略。37穷举法中的无效计算以i为起点的子序列：D[i...i]、D[i..i+1]、...、D[i...n]，每次都从第一个元素开始进行累加，存在大量重复运算。4

beginres←-∞;

//初值为负无穷大for

i←1

to

n

do

//i为子序列起点for

j←i

to

n

do

//j为子序列终点sum←09 for

k←itojdo

//子序列求和10 sum←sum+D[k]11end

forres←MAX(res,

sum)end

forend

for输出res16end

begin示例：D[1...13]之和与D[1...14]之和的重复计算38优化思想之一：“累加和”相减u累加和序列S[0...n]：元素S[i]为序列D[1...n]中前i个元素之和。u子序列D[i...j]之和

=

S[j]

-

S[i-1],

1≤i≤j≤n。为什么可以提高效率：一次循环O(n)时间完成序列S的构造，一次减法O(1)时间计算任意子序列之和39利用“累加和”的优化算法算法10.3

最大子序列和问题的优化算法一Input:大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-3(D[1...n])begin//i为子序列起点//构造序列S的第i个元素//初值为负无穷大//i为子序列起点forj←itondo //以i为起点的第2到最后一个子序列的循环5 初始化大小为n+1的序列S[0...n]

6 S[0]←07 fori←1ton

do8 S[i]←S[i-1]+D[i]end

forres←-∞fori←1ton

do12sum←S[j]-S[i-1]

//利用序列S计算子序列D[i...j]之和res←MAX(res,

sum)

//确保res为最大值end

forend

for输出res18end

begin构造“累加和”序列S“累加和”一次构造，多次使用时间复杂度为：T(n)=

O(n2)40算法10.3中的无效计算10 res←-∞//初值为负无穷大11 fori←1ton

do//i为子序列起点12for

j←iton

do//以i为起点的第2到最后一个子序列的循环1314sum←S[j]-S[i-1] //利用序列S计算子序列D[i...j]之和res←MAX(res,

sum)//确保res为最大值15end

for16 end

foru

遍历解空间是最基本的问题求解方法。u

有很多巧妙的算法策略，可以更高效地在解空间中搜索问题的解，不需要遍历整个解空间。依然是对解空间中所有可能解进行遍历的算法还有更好的办法吗41一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择优化思想之二：问题分解42优化思想之二：问题分解问题分解是一种将大的问题分解为若干个更小的子问题的方法，如果子问题的形式与原问题相同，可用递归方法完成子问题的求解。n 子问题规模必须要小于原问题n 如果子问题的形式与原问题相同，可以利用递归求解子问题n 要建立原问题与子问题之间的联系n 要分析清楚什么是可以直接求解的最小子问题43最大值子序列和问题的分解原问题的解只可能是下面的三种情况之一：u

“解”完全在左半部分即D[1...7]中，因此结果等于f(1,7);u

“解”完全在右半部分即D[8...14]中，因此结果等于f(8,14);u

“解”跨越了中线，一部分在左半部分，另一部分在右半部分，记为g(1,7,14)。f(1,7)、f(8,14)与f(1,14)属于同类问题；g(1,7,14)属于新问题求出3个子问题的解，其中的最大值就是原问题的解44跨越中线子问题g(1,7,14)的求解方法u

以中线位置为起点向左进行累加，在累加过程中筛选左半部分的最大值lsum；u

以中线位置为起点向右进行累加，在累加过程中筛选右半部分的最大值rsum;u

g(1,7,14)的最终结果为lsum+rsum=25。上述两个累加操作的时间复杂度为O(n)。45跨越中线子问题的伪代码算法10.4

最大子序列和问题的优化算法二Input:

子序列的起点i、终点j、中间位置kOutput:

跨越中线的最大的子序列和functiong(i,k,j)

//跨越中线的子问题beginlsum←-∞ //中线到左边的最大子序列sum←0fort←kdowntoi

dosum←sum+D[t]lsum←MAX(lsum,

sum)end

forrsum←-∞

//中线到右边的最大子序列sum←0fort←k+1toj

dosum←sum+D[t]rsum←MAX(rsum,

sum)end

forreturn

lsum+rsum18end

begin求左半部分最大值求右半部分最大值时间复杂度为：T(n)=

O(n)46自顶向下分解形成分解树f类问题一直分解下去，形成最小子问题，最小子问题只有一个元素，元素的值就是解。g类问题每层都有，实际累加计算都发生在g类问题中。47子问题的解自底向上合并形成更大子问题的解最底层的f类问题、以及所有的g类问题都可直接求解，求最大值后可依次合并出上一层的解；一直进行下去，合并出原问题（最顶层）的解。48基于“问题分解”的优化算法ifi=j

then

//最小子问题returnD[i]endif26 k←⌊

(i+j)/2⌋ //计算中线位置27 returnMAX(f(i,k),f(k+1,j),

g(i,k,j)

) //从中线分解问题算法10.4最大子序列和问题的优化算法二Input: 子序列的起点i、终点jOutput:

子序列D[i...j]的最大的子序列和21

function

f(D[1...n],i,j)

//形式相同的子问题22

beginendbeginInput: 大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-4(D[1...n])beginres←f(1,n) //原问题输出res35end

begin最小子问题/递归函数出口问题分解与合并/递归调用调用递归函数求解问题时间复杂度是多少？49算法10.4的时间复杂度分析u算法的分解树共有logn层u每一层g函数处理的序列合并起来就是原序列，相当于对原序列进行了一次累加，是O(n)的操作。u总的时间复杂度是O(nlogn)50算法10.4是分治策略分治策略是一种利用问题分解求解问题的策略，其核心思想是分而治之，求解问题时采用分、治、合三个步骤：u

分：将复杂问题分解为与原问题形式相同的、规模更小的独立子问题，子问题可以一直分解下去；u

治：直接求解最小子问题；u

合：将已经求解的子问题的解进行逐层合并，最后得到原问题的解。算法10.4的“分”：将问题分解为2个形式相同的子问题和1个形式不同的子问题；算法10.4的“治”：求解最小的f类子问题，以及g类子问题的解；算法10.4的“合”：合并f类问题和g类问题的解，得到上一层子问题的解。51算法10.4中的无效计算u

分解树共有logn层u

共对原序列进行了logn次重复的累加还有更好的办法吗52一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择优化思想之三：解空间划分53优化思想之三：解空间划分u将序列D[1...n]的所有子序列根据末尾元素的不同分为n个子集。例如，以D[3]结尾的子集为{D[3...3],

D[2...3],

D[1...3]}；u分别对每个子集进行遍历并求出最大子序列和，记为T[1]、T[2]、...、T[n]，例如T[3]是子集{D[3...3],D[2...3],D[1...3]}的最大子序列和，结果为max(-20,-12,1)=

1。u序列T[1...n]中的最大值就是问题的解，T[10]为25，是序列T的最大值，因此是问题的解。如何提高效率：如果生成序列T的效率高，算法的效率就很高54求序列T的方案一：穷举法u一个T[i]的计算方法：遍历所有“以第i个元素结尾的子序列”（起点为k=1，2，...i），分别计算其元素之和，然后取最大值为结果：

T[i]

=

max(S[i]

-

S[k-1]),

k=1,

2,

...

i，S[0...n]为“累加和”序列。u所有T[i]的计算方法：i从1循环到n，依次计算T[i]。求一个T[i]需要进行i次减法运算，时间复杂度为O(n)求所有T[i]的时间复杂度为O(n2)，比算法10.4更差55求序列T的方案二：优化方案uT[i]=max(S[i]-S[k-1]),

k=1,2,

...

i(k是子序列起点，i是终点)u若能找到所有S[k-1]中的最小值，即可得到S[i]-S[k-1]的最大值，即：T[i]

=

S[i]

-

min(S[k-1]),k=1,2,...

iu构造最小累加和序列M

，

令M[i]为序列S[0...i]的最小值，则M[i-1]为序列S[0...i-1]的最小值，即min(S[k-1])，则：T[i]=S[i]-

M[i-1]u

序列M的生成方式：M[i]=min(M[i-1],

S[i])M序列的生成可在O(n)时间内完成求一个T[i]需要进行1次减法运算，时间复杂度为：O(1)求所有T[i]的时间复杂度为O(n)，比算法10.4更优56基于“解空间划分”的优化算法构造序列T时间复杂度为：T(n)

= O(n)构造“累加和”序列S构造序列M序列T的最大值为问题的解算法10.5

最大子序列和问题的优化算法三1

Input:大小为n的顺序表D[1...n]2

Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-5(D[1...n])begin//构造序列S的第i个元素初始化大小为n+1的序列S[0...n]和M[0...n]初始化大小为n的序列T[1...n]

7 S[0]←08 fori←1ton

do9 S[i]←S[i-1]+D[i]10 endfor

11 M[0]←0fori←1ton

doM[i]←MIN(M[i-1],S[i])

//构造序列M的第i个元素end

forfori←1ton

doT[i]←S[i]-M[i-1]

//利用序列S和序列M计算T[i]end

forres←-∞ //最终结果，初值为负无穷大fori←1ton

dores←MAX(res,

T[i])end

for输出res23end

begin57算法10.5的空间优化：省略序列Tu最终目的是找出所有T[i]中的最大值；u每次完成S[i]-M[i-1]计算时，不保存到T[i]

，直接与res竞争；去掉构造序列T的循环，并省略序列Tres←-∞fori←1ton

dores←MAX(res,

S[i]-M[i-1])end

for计算结果不保存到T[i]，直接与res竞争res←-∞fori←1ton

dores←MAX(res,

T[i])end

for58算法10.5的空间优化：省略序列Mu第i次循环时，仅需访问