欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计算机算法设计与分析——算法引论

程序员文章站 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 次;

平均比较次数:计算机算法设计与分析——算法引论

统计执行步数:按程序步、执行语句统计

计算机算法设计与分析——算法引论

相关标签: 计算机算法设计

上一篇:

下一篇: