算法设计与分析 （知识点总结）

    通过学习掌握算法设计的主要方法，对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构并设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。

1.什么是算法？     算法(algorithm):算法是对特定问题求解步骤的描述，是指令的有限序列。就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。 2.算法的五个特征

3.问题和问题求解     问题求解：寻找一种方法来实现目标。     问题求解过程：人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识求选择和使用适当的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。     计算机求解问题的关键之一是寻找一种问题求解策略得到求解问题的算法，从而得到问题的解。 4.问题求解过程

1.算法问题求解过程 2.算法分类     精确算法总能保证求得问题的解。     启发式算法通过使用某种规则、简化或智能猜测来减少问题求解时间。     对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法。     如果在算法中需要做出某些随机选择，则称为随机算法。 3.算法设计

4.算法表示

算法描述方法

5.算法确认

6.算法分析

1.什么是好的算法

    一个好的算法应具备以下4个重要特性：

    程序健壮性：是指当输入不合法数据时，程序可以做适当处理而不至于引起严重后果。 其含义是：当程序万一遇到意外时，能按某种预定方式作出适当处理。

    正确性和健壮性是相互补充的。

2.影响程序时间的因素

    影响程序运行时间的因素主要有：

程序所依赖的算法；

问题规模和输入数据；

计算机系统性能 3.算法的时间复杂度

抽象机模型     设抽象机提供由m个基本运算组成的运算集O={O1,O2,…,Om}，每个运算都是元运算，（运算亦称演算，数学的基本概念之一，指使的一些计算规则，算术中有加、减、乘、除、乘方、开方六种运算，其中加、减、乘、除是从两个已知数得出第三个数的运算，称为二元运算；乘方、开方是从一个已知数得出另一个数的运算，称为一元运算）。 它们的执行时间是有限常量。设执行第i个运算Oi所需的时间是αi，1≤i≤m。 一个算法给定一个输入并在抽象机上执行一次，该执行过程表现为执行一个基本运算序列。

时间复杂度     算法的时间复杂度是指算法运行所需的时间。     设有一个在抽象机上运行的算法A，I是某次运行时的输入数据，其规模为n，则算法A的运行时间T是n和I的函数，记做T(n,I)。又设在该次运算中抽象机的第i个基本运算Oi的执行次数为βi，1≤i≤m。βi也是n和I的函数，记做βi(n,I)。那么算法A在输入为I时的运行时间是：

最好、最坏和平均时间复杂度：

最好时间复杂度

最坏时间复杂度

平均时间复杂度（与概率论中的数学期望概念类似，在概率论和统计学中，期望值（或数学期望、或均值，亦简称期望，物理学中称为期待值）是指在一个离散性随机变量试验中每次可能结果的概率乘以其结果的总和。换句话说，期望值是随机试验在同样的机会下重复多次的结果计算出的等同“期望”的平均值。 ） 4.算法分析

事前分析：在算法实际运行前分析算法的效率。

事后测试：运行程序来测试一个程序在所输入数据下实际运行的时间。

程序步：在语法或语义上有意义的程序段，该程序段的执行时间必须与问题实例的规模无关。

实例 5.算法的空间复杂度

算法的空间复杂度：算法运行所需的存储空间。

程序运行所需的存储空间包括以下两个部分：

固定空间需求：这部分空间与所处理数据的大小和个数无关，即与问题实例的特征无关。

可变空间需求：这部分空间大小与算法在某次执行中处理的特定数据的规模有关。

1.大O记号     定义：设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n)=O(g(n))，称为大O记号。     意义：该算法的运行时间 不会超过 g(n)的某个常数倍。 g(n)是该算法运行时间的上界。

2.Ω 记号     定义：设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≥cg(n)，则记做f(n)=Ω (g(n))，称为Ω记号。     意义：该算法至少需要g(n)的某个常数倍大小的时间量。g(n)是该算法运行时间的下界。 例题1： 例题2： 3.Θ记号     定义：设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1,c2和n0，使得当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，则记做f(n)=Θ(g(n))，称为Θ记号。     意义：该算法实际运行时间大约为g(n)的某个常数倍大小的时间量。（有上界也有下界） 例题1： 4.小o记号     定义：f(n)=o(g(n))当且仅当f(n)=O(g(n))且f(n)≠ Ω(g(n))     意义：该算法的运行时间f(n)的阶比g(n)低。

5.算法按时间复杂度分类

算法按计算时间分类     渐近时间复杂度有多项式时间限界的算法称做多项式时间算法。     渐近时间复杂度为指数函数限界的算法称做指数时间算法。

最常见的多项式时间算法的渐近时间复杂度     O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n2)＜O(n3)

最常见的指数时间算法的渐近时间复杂度      O(2n)＜O(n!)＜O(nn)