计算机算法设计与分析——算法引论
程序员文章站
2023-12-27 10:37:51
...
1.1 算法与程序
计算机算法
通俗定义:用计算机求解问题的方法或过程。
正式定义:算法是满足下述性质的 指令序列:
- 输入:有零个或多个外部量作为算法的输入
- 输出:至少产生一个量作为输出
- 确定性:组成算法的每条指令是清晰的、无歧义的
- 有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限
1.2 算法的抽象与描述
算法的的抽象
- 选用该问题的一个数据模型
- 明确初始状态和已知状态
- 描述数据模型级运算步骤:暂不关心变量的数据结构,运算不含细节。可用伪码描述。
- 算法实现:依赖具体数据结构、具体语言。
算法的描述
- 可以使用C、C++、JAVA等高级计算机语言描述,好处是可以利用语言的抽象数据类型,易于检验逻辑错误。
- 伪码描述:描述算法最重要的是表达清楚算法的基本思想和关键过程,高级语言涉及实现细节,对算法描述并非都是必要的。
ALGEN语言
- 变量:提供int,real,bool,char等简单变量。赋值:v:=expr
- A[1..n]表示长为n的一维数组;A[1..m,1..n]表示二维数组。
- for、While和Loop循环
- break、continue、exit、go to
- If和case条件语句
- 子程序:proc name(formal parameters)
- 允许使用自然语言和数学表达式
1.3 空间复杂性
考虑空间复杂性的理由
- 在多用户 系统中运行时,需指明分配给该程序的内存大小;
- 想预先知道计算机系统是否有足够的内存来运行该程序;
- 用空间复杂性来估计一个程序可能解决的问题的最大规模;
- 一个问题可能有若干个不同的内存需求解决方案,从中 择优;
程序需要的空间
- ①指令空间、②数据空间、③环境栈空间。
- 程序空间与算法、编译和目标机相关,空间复杂性分析主要关注算法相关的空间要求。
例子:
template<class T> template<class T>
T Sum( T,a[ ], int n ) T Rsum( T a[ ], int n)
{//计算 a[0:n-1]的和 {//计算a[0:n-1]的和
T tsum=0; if (n>0)
for(int i=0, i<n; i++) return Rsum(a,n-1)+a[n-1];
tsum+=a[i]; return 0;
return tsum; }
}
//存数组的地址a, //保留a的地址,函数返回地址,
//变量n, i, tsum: //存储变量n , 递归深度为 n+1
//Ssum=2+4+4+sizeof(T) //Srsum=(2+2+4)(n+1) +sizeof(T)
//2为a[]指针,4为n和i,tsum T //2,2是a[]和返回的[],4为n,(n+1)递归
1.4 时间复杂性
考虑时间复杂性的理由
- 某些计算机用户需要提供程序运行时间的上限
- 把握问题求解的难易程度,清晰划分问题的可求解范围
- 评价算法的优劣,改进算法。
时间复杂度的度量:关键操作计数、总的执行步统计
- 用基本运算次数(约定每种基本操作所用时间都是一个单位)衡量算法的效率。(不能用机器的真正运行时间作为度量标准)。
- 算法的运算次数与实例规模有关,复杂度函数:T(n)
- 对规模为n的两个不同实例,如何选择T(n)?
- 最坏情况下的时间复杂度W(n)
- 平均情况下的时间复杂度A(n)
例1:寻找数组中最大元素,关键操作n-1次
template<class T>
int Max(T a[], int n)
{//寻找a[0:n-1]中的最大元素
int pos=0;
for (int i=1; i<n; i++)
if (a[pos]<a[i])
pos=i;
return pos;
}
这里的关键操作是比较。for循环*进行了n-1次比较
例2:n次多项式求值程序:基本操作3n次
template<class T>
T PolyEval(T coeff[], int n, const T &x)
{//计算n次多项式的值,coeff[0:n]为多项式的系数
T y=1, value=coeff[0];
for (int i=1; i<=n; i++) //n循环
{ //累加下一项
y*=x; //一次乘法
value+=y*coeff[i]; //一次加法和一次乘法
}
return value;
} //3n次基本运算
这里的关键操作是数的加法与乘法。
例3:顺序查找
template < class T >
int SeqSearch (T a[ ], const T &x, int n)
{ //在a[0:n-1]中搜索x,若找到则返回所在的位置,
否则返回-1
int i;
for (i=0; i<n && a[i]!= x; i++);
if (i==n) return -1;
return i;
}
最好情况:比较 1 次;
最坏情况:比较 n 次;
平均比较次数:
统计执行步数:按程序步、执行语句统计