算法与算法分析

目录

一.前言

二.算法的特性和要求

三.分析算法--时间效率

四. 分析算法--空间效率

一.前言

        算法就是对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中，每个指令表示一个或多个操作。总而言之，我们数据结构就是通过算法实现操作。而我们的算法又是根据数据结构来设计程序。程序=数据结构+算法。

二.算法的特性和要求

        算法一共有五个特性：有穷性，确定性，可行性，输入，输出。其中输入输出就是我们的算法一定要有输入和输出。

        算法设计的要求有四个，分别是正确性，可读性，健壮性，高效性。其中健壮性就是指我们在输入非法数据的时候，算法恰当的作出反应或进行相应处理，而不是产生莫名其妙的大额输出结果。

三.分析算法--时间效率

        我们评价一个算法的好坏主要从它的算法效率来看，而算法效率又可以通过以下两个方面来考虑：时间效率和空间效率。尽管二者有时候是矛盾的。

        我们首先来分析下时间效率。通过分析可以得到：

其中，每条语句的执行次数我们也称作语句的频度。 

        由于算法中每条语句执行一次所需的时间是由机器本身软硬件环境决定的，所以我们可以假设执行每条语句所需的时间均为单位时间。

        在知道了这个知识点之后，后面我们在进行算法之间的比较的时候，我们一般可以把语句执行一次所需的时间看成1，不影响算法的时间效率。所以我们通常把算法所耗费的时间定义为该算法中每条语句的频度之和，也就是执行次数之和。

下面我们来看一个简单的案例：

for(int i=1;i<=n;i++){   //执行n+1次
    for(int j=1;j<=n;j++){    //执行n*(n+1)次
        a[j]=a[i]+j;        //执行n*n次
    }
}

我们来分析下上面这段算法，分析它的时间效率。所以我们可以考虑得出这个算法每条语句的频度。第一行的代码会执行n+1次，因为在执行完n次之后，虽然i已经等于n+1次了，但它还是得继续判断i是否小于等于n，然后不满足条件才结束循环。所以总共会执行n+1次。同理，第二行代码外层循环每执行一次，它就执行n+1次，而外层循环总共执行n次（因为在执行第n+1次的时候，i>n，不满足条件），所以第二行代码的语句频度为n*(n+1)。第三行代码则执行n*n次。

综上所述，所以我们上面这个算法的运行时间也就是T(n)=n*n+n*(n+1)+n+1=2n*n+2n+1。

        由于我们这里的n次，具体的数值我们并不清楚，n可能很小，也可能很大。所以在这里我们需要引入渐进时间复杂度的概念。如下所示：

也就是说，我们为了方便比较不同算法的时间效率，我们仅仅比较它们的数量级。

        通过分析我们可以看出，算法中执行次数最多的那条语句往往就是我们时间复杂度的不去除系数的数值。所以下面我们来介绍下分析算法时间复杂度的基本方法：

1）首先找出语句频度最大的那条语句作为基本语句。

2）计算基本语句的频度得到问题规模n的某个函数f(n)

3) 取它的数量级并用符号"O"表示。

4）最后，时间复杂度T(n)=O(f(n))

         接着我们介绍一种特殊情况，也就是算法基本操作执行的次数还随问题的输入数据集不同而发生变化。所以这里我们需要引入平均时间复杂度的概念。

平均时间复杂度也就是指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间。

        最后，我们在得到了时间复杂度之后，我们该怎么评价它的复杂度呢？这里就涉及到复杂度的大小顺序了，如下所示：

从左到右，复杂度依次递增。

四. 分析算法--空间效率

        所谓算法的空间效率我们可以用算法的空间复杂度来衡量，也就是算法所需存储空间的度量。记作S(n)=O(f(n))。其中n为问题的规模，f(n)也就是上面所介绍的基本语句的执行次数所对应包含n的函数，这里把执行次数换成了空间大小。

        那我们算法所占用的空间有哪些呢？总共分为两种：一种就是算法本身要占据的空间，输入/输出，指令，常数，变量等。第二种就是算法要使用的辅助空间。我们看下面两个案例：

for(int i=0;i<n/2;i++){
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}

上面这段代码由于只使用了t这一个辅助空间，因此它的空间复杂度就是1，也就相当于原地工作。

而我们接着看下面这段代码：

for(int i=0;i<n;i++){
    b[i]=a[n-i-1];
{
for(int i=0;i<n;i++){
    a[i]=b[i];
}

 这段代码由于使用了数组b作为辅助空间，所以它的空间复杂度就不再为1,而是为数组b的大小，也就是n,即S(n）=O(n)。