第一章绪论——算法分析初步（三）
1.1 算法
算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有以下五个特性
① 有穷性： 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
② 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
③ 可行性： 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。
④ 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。
⑤ 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。
算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。
1.2 算法设计的要求
评价一个好的算法有以下几个标准
① 正确性(Correctness )： 算法应满足具体问题的需求。
② 可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。
③ 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。
4、通用性(Generality)： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合都成立。
⑤ 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。
1.3 算法效率的度量
进行度量的两种方法
事后统计：计算机内部进行执行时间和实际占用空间的统计。
问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。
事前分析：求出该算法的一个时间界限函数。
算法分析应用举例
算法中基本操作重复执行的次数是问题规模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(㏒n) ：对数时间阶 O(n㏒n) ：线性对数时间阶
O (nk)： k≥2 ，k次方时间阶
例１两个n阶方阵的乘法
for(i=1，i<=n; ++i)
for(j=1; j<=n; ++j) {
c[i][j]=0 ;
for(k=1; k<=n; ++k)
c[i][j]+=a[i][k]*b[k][j] ; }
由于是一个三重循环，每个循环从1到n，则总次数为： n×n×n=n3 时间复杂度为T(n)=O(n3)
例２：{++x; s=0 ;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。 如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。
例３ for(i=1; i<=n; ++i) { ++x; s+=x ; } 语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。
例４
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
{ ++x; s+=x ; } 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。
定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)
例５ 存疑：语句频度的计算
for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{++x; a[i,j]=x; }
语句频度为： 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) 空间复杂度(Space complexity) ：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。 记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间; 输入数据所占用的存储空间; 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 一维数组a[n]： 空间复杂度 O(n) 二维数组a[n][m]： 空间复杂度 O(n*m)1.4 算法的空间分析