数据结构算法和算法分析

算法的描述：

1:自然语言：英语，中文

2:流程图：传统流，NS流程图

3:伪代码：类语言，类c语言

4:程序代码：c语言程序，java语言程序

算法：

       是解觉问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法

程序：

       是用某种程序设计语言对算法的具体实现。

程序=数据结构+算法

算法的定义：

       1：有穷性

       2：确定性

       3：可行性

       4：输入，输出。

算法设计的要求：

     1：正确性

     2：可读性

     3：健壮性

     4：高效性。

若是以上都要求：则主要考虑算法的效率：

    时间效率：算法所耗费的时间

    空间效率：算法所耗费的存储空间

算法的时间效率度量：两种

        事后统计：将算法实现测算其时间和空间开销

        事前分析：对算法所耗资源的一种估算方法

一个算法运算时间：

          每条语句频率（每条语句执行的次数）* 该语句执行一次所要的时间

          算法的执行时间大致上等于其所有语句执行时间的总和。

算法的时间复杂度定义：

          一般情况下，算法中基本语句重复执行的次数是问题规模n的每个函数f（n），算法的时间量度记作:T(n)=O(f(n))

算法的时间复杂度分析：

        1：找出所有语句中语句频率最大的那条语句作为最基本语句，

        2：计算基本语句的品读得到问题规模你的每个函数f(n）

        3：取其数量级用符号“O”表示即可。

若是f(n)是一个m次多项式，则T(n)=O(n的m次方）。

平方实例：

      (1) x=0;y=0;       

      (2) for (k=1;k<=n;k++)      //执行n次

      (3)      x++;                        //执行n次

      (4)  for(i=1;i<=n;i++)           //执行n次

      (5)     for(j=1;j<=n;j++)         //执行n次

      (6)          y++;                       //执行n*n次

所以综上所述频率最大的语句是（6），其频道为f(n)=n*n,所以该算法的时间复杂度为：T(n)=O(n*n),称为平方阶。

算法空间复杂度：

关于算法的存储空间要求

S(n)=O(f(n)),其中n为问题的规模（或大小）

例题（二）：

i=1;

while(i<=n)

    i=i*2;

以上若是执行一次为2，两次为2的平方，三次为2的3次方，若是循环x次则为：i=2的x次方

因为：i<=n , 所以:2的x次方<=n , 所以 x<=log以2为底n的对数。

即f(n)<=log以2为底n的对数。最大值：f(n)=log以2为底n的对数。

T(n)=O(log以2为底n的对数)