数据结构与算法——算法和算法分析

目录

1.算法分析概述

2.计算算法时间复杂度的基本方法

3.特殊算法的时间复杂度

4.难以求出的时间算复杂度

1.算法分析概述

        算法分析就是分析算法占用计算机资源的多少。计算机资源主要是cpu时间和内存空间，分析算法占用cpu时间的多少称为时间性能分析，分析算法占用内存空间的多少称为空间性能分析。

        算法分析的目的是分析算法的时间空间性能以便改进算法

2.计算算法时间复杂度的基本方法

        1.找出基本频度最大的那条语句作为基本语句

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

        3.取其数量级用符号"O"表示

例如：(这里代码并不是完整的代码，只是为了说明求解的方法，写出来重要的几步)

for(i=0;i<=n;i++)
    for(j=1;j<=i;j+++)
        for(k=1;k<=j;k++)
                x=x+1;

语句平度=

=n(n+1)(n+2)/6

n的最高次幂为n的三次方   所以：

                                                               T(n)=O(

)

例如：

i=1;        //(1)
while(i<n)
    i=i*2        //(2)

 (1)若循环执行次数为1次：i=1*2=2

     若循环执行次数为2次：i=2*2=2^2

     若循环执行次数为3次：i=2^3

     若循环执行次数为n次：i=2^x

设语句（2）执行次数为x次

i<=n;

所以2^x=n  即x<=

取最大值f(n)=log

时间复杂度T(n)=O(log

) ==>o(lgn)

3.特殊算法的时间复杂度

        有的情况下，算法基本操作重复执行的次数还随问题的输入数据集不同而不同

例如：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。

for(i=0;i<n;i++)
    if(a[i]==e)
        return i+1;
    return 0;

最好情况：1次

最坏情况：2次

平均时间复杂度为：O(n)

所以分析时间复杂度为多少一般考虑（1）和（2）

（1）最坏时间复杂度：

        指在最坏情况下，算法的时间复杂度。

（2）平均时间复杂度：

        指在所以可能输入实列在等概率出现的情况下，算法的期望运行的时间

（3）最好时间复杂度

        指在最好情况下，算法的时间复杂度

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会更长。

4.难以求出的时间算复杂度

        有的算法比较复杂，O(n)很难表示

对于复杂的算法，可以将他分成几个容易估计的部分，然后利用O加法法则和乘法法则，计算算法的时间复杂度：

a）加法法则

T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n))

b)乘法法则

T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O((f(n)×g(n))

算法时间效率比较：

        当n取得很大时，指数时间算法和多项式时间算法在所需时间非常悬殊

算法时间复杂的由低到高

在设计程序时候应该考虑算法时间复杂度较低的程序

5.渐进空间复杂度

空间复杂度：

        算法所需存储空间的度量

                记作：s(n)=O(f(n))

其中n为问题的规模（或大小）

算法占据的空间

-->算法本身要占据空间，输入/输出，指令，常数，变量等。

-->算法要使用的辅助空间

eg：将一堆数组a中的几个数逆序存放到原数组中：

算法1:

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

算法2：

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

}

算法1的时间复杂度S(n)=O(1)        常数阶

算法2的时间复杂度S(n)=O(n)        一次阶

所以算法1比算法2更好