1.4 算法与算法分析
视频二维码（扫码观看）
一、算法
算法（Algorithm）：是对特定问题求解方法（步骤）的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有以下五个特性：
①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
②确定性：算法中每一条指令必须有确切的含义，不能存在二义性。且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。
算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法具有有穷性，程序可以在无限循环中执行，这意味着不是所有的计算机程序都是算法。
二、算法设计的要求
评价一个好的算法有以下几个标准：
①正确性（Correctness）：算法应满足具体问题的需求。
②可读性（Readability）：算法应容易供人阅读和交流。可读性好的算法有助于人对算法的理解和修改。
③健壮性（Robustness）：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
④通用性（Generality）：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。
⑤效率与低存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。
三、算法效率的度量
算法执行时间通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：
（1）事后统计
计算机内部进行执行时间和实际占用空间的统计。
缺陷：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。
（2）事前分析
求出该算法的一个时间界限函数。时间取决于下列因素：
①依据算法选用何种策略；
②问题的规模；
③程序设计的语言；
④编译程序所产生的机器代码的质量；
⑤机器执行指令的速度；
撇开软硬件等有关部分因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。
算法中基本操作重复执行的次数是问题规模n的某个函数f（n），其时间量度记作T（n）＝O（f（n）），称作算法的渐近时间复杂度（Asymptotic Time complexity），简称时间复杂度。
一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。“O”的定义：若f（n）是正整数n的一个函数，则O（f（n））表示∃M≥0，使得当n≥n0时，|f（n）|≤M|f（n0）|。
表示时间复杂度的阶有：
①O（1），常量时间阶
②O（n），线性时间阶
③O（logn），对数时间阶
④O（nlogn），线性对数时间阶
⑤O（nk），k≥2，k次方时间阶
【例1】两个n阶方阵的乘法。
由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n＝n3，时间复杂度为T（n）＝O（n3）。
【例2】{++x;s=0;}
将x自增看成是基本操作，则语句频度为1，即时间复杂度为O（1）。如果将s＝0也看成是基本操作，则语句频度为2，其时间复杂度仍为O（1），即常量阶。
【例3】for(i=1;i<=n;++i){++x;s+=x;}
语句频度为：2n，其时间复杂度为：O（n），即为线性阶。
【例4】
语句频度为：2n2，其时间复杂度为：O（n2），即为平方阶。
【定理】若A（n）＝amnm＋am－1nm－1＋…＋a1n＋a0是一个m次多项式，则A（n）的时间复杂度为O（nm）。
【例5】
语句频度为：1＋2＋3＋…＋n－2＝（1＋n－2）×（n－2）/2＝（n－1）（n－2）/2＝n2－3n＋2。
时间复杂度为O（n2），即此算法的时间复杂度为平方阶。
一个算法时间为O（1）的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O（n2）的算法则由一个二次多项式来限界。
以下六种计算算法时间的多项式是最常用的。其关系为：
O（1）＜O（logn）＜O（n）＜O（nlogn）＜O（n2）＜O（n3）
指数时间的关系为：O（2n）＜O（n!）＜O（nn）
当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。
【例6】素数的判断算法。
嵌套的最深层语句是i＋＋；其频度由条件（（n%i）!＝0&&i*1.0＜sqrt（n））决定，显然i*1.0＜sqrt（n），时间复杂度O（n1/2）。
【例7】起泡排序法。
最好情况：0次。
最坏情况：1＋2＋3＋⋯＋n－1＝n（n－1）/2。
平均时间复杂度为：O（n2）。
四、算法的空间分析
空间复杂度（Space complexity）：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S（n）＝O（f（n）），其中：n为问题的规模（或大小）。
该存储空间一般包括三个方面：
①指令常数变量所占用的存储空间；
②输入数据所占用的存储空间；
③辅助（存储）空间。
算法的空间复杂度指的是辅助空间。
一维数组a[n]：空间复杂度O（n）。
二维数组a[n][m]：空间复杂度O（n*m）。