国立中山大学算法设计与分析

时间：2018-03-28 13:44:09 由 lyp 分享

内容简介

国立中山大学算法设计与分析视频简介：

　　算法设计与分析包含的内容广泛，既包括高级的算法设计主题，也包括概率分析以及最新的分摊分析和实验分析方法等内容，是高等教育中，数学教育的重要内容。下面我们就来了解一下。

　　基本内容

　　按照算法所处理的对象进行分类，算法设计与分析主要有数值算法和非数值算法两大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值计算
关注公众号:diyijc_com 问题反馈

教程内容

国立中山大学算法设计与分析视频简介：

　　基本内容

　　按照算法所处理的对象进行分类，算法设计与分析主要有数值算法和非数值算法两大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值计算的算法问题。非数值算法主要包括整序搜索、几何问题的计算、离散结构的计算、模式匹配等有关非数值计算的算法问题。

　　按照计算方式进行分类，则可分为串行算法和并行算法，还可以分为确定型算法、非确定型算法、交错型算法、随机型算法等(见计算复杂性理论)。

　　另外，还有关于近似算法的研究。对于已经证明不存在快速算法，或者至今还未找到快速算法的问题，例如NP完全问题(见NP完全性), 与其花费大量的时间去寻找精确解，不如花费少量的时间去寻找近似解。

　　基本概念

　　设计算法与分析算法的复杂度，都与计算模型有关，大多属于随机存取机器模型，这是一种确定型的串行计算模型。

　　随机存取机器是一种理想的计算机，由一个累加器、一个存储器和一个程序组成。存储器具有无限多个寄存器，每个寄存器可以存放任意大的一个自然数。程序是由一些最基本的指令所组成的序列，这些指令通常是指包括直接寻址与间接寻址在内的加、减、乘、除、取数、存数、条件转移和停机。所有的运算和逻辑判断都在累加器中进行。

　　问题的大小，也称问题的规模，通常用一个自然数作为随机存取机器输入数据量多少的度量。

　　时间复杂度和空间复杂度分别表示对于规模为 n的输入问题、随机存取机器所耗费的时间与空间，它们都是 n的函数。常用的时间和空间的度量方式是均匀耗费标准：执行一条指令算作耗费一个单位的空间，使用一个寄存器算作耗费一个单位的空间;另一种度量方式是对数耗费标准(见随机存取机器模型)。复杂度函数的计算方式又有两种：规模为n的所有问题的复杂度的最大值称为最环情况复杂度;规模为n的所有问题的复杂度的平均值称为平均情况复杂度。当规模n增加时,复杂度的量级即极限属性称为渐近复杂度。由于理论计算机与现实计算机之间的差异，以及不同的现实计算机之是的差异，也由于算法设计与分析主要关心规模 n比较大的情况，通常讨论的是渐近复杂度。

更新时间：2013-10-30 17:25