您的位置:首页 > 游戏 > 游戏 > 数据结构算法和算法分析

数据结构算法和算法分析

2024/11/17 20:19:53 来源:https://blog.csdn.net/2401_83201682/article/details/142068779  浏览:    关键词:数据结构算法和算法分析

算法的描述:

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的对数)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com