算法设计与分析

前言

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

第一章 算法基础

1.1 算法概述

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

• 输入：算法有零个或多个输入量；
• 输出：算法至少产生一个输出量；
• 确定性：算法的每一条指令都有确切的定义，没有二义性；
• 可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；
• 有穷性：算法必须执行有限步之后终止。

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

• 理解问题
• 设计方案
• 实现方案
• 回顾复查

1.2 算法分析

1.算法问题求解过程

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

• 计算机的问题求解策略主要指算法设计策略。
• 如果所求问题符合某种算法设计策略处理问题的特性，就可使用该算法设计策略设计算法、求解问题。

4.算法表示

算法描述方法

• 自然语言
• 流程图
• 伪代码
• 程序设计语言
• 使用c/c++语言描述

5.算法确认

• 算法确认：确认一个算法是否正确的活动。
• 算法证明：使用数学方法证明算法的正确性。
• 程序测试：是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求和活动。

6.算法分析

• 算法分析：对算法的执行时间和所需空间的估量。（时间复杂度和空间复杂度）
• 程序的性能测量：使用样本数据，实际测量一个程序所消耗的时间和空间。

1.3 算法复杂度

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.4 渐近表示法

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

• 渐进时间复杂度
      使用大O记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度。
      只要适当选择关键操作，算法的渐近时间复杂度可以由关键操作的执行次数之和来计算。一般地，关键操作的执行次数与问题的规模有关，是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)
  

第二章 分治法