注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

周响 廊坊师范学院九期信息技术提高班

一个世界有你 一个世界没有你 让两者的不同最大 就是你一生的意义

 
 
 

日志

 
 

数据结构总结一  

2012-05-29 08:10:27|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数据结构总结一 - 周响 - 周响  廊坊师范学院九期信息技术提高班
 数据结构总结一 - 周响 - 周响  廊坊师范学院九期信息技术提高班
数据结构总结一 - 周响 - 周响  廊坊师范学院九期信息技术提高班

  

数据元素之间的关系在计算机中有两种不同的表示方法(存储方法):顺序存储和链式存储

顺序存储与链式存储的优缺点

存储密度=信息实际所占空间/实占内存空间空间

顺序存储;存储密度等于1,可实现随机访问,增加、删除困难

链式存储:存储密度小,经常需要插入、删除结点,随机访问困难,存在附加信息

算法:为解决某问题而采取的具体的,有限的操作步骤。

算法的特性:有穷性、确定性、可行性、输入、输出

算法设计的要求:正确性、可读性、健壮性、效率与低存储量

算法效率的度量通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。

  1. 事后统计法

    事后统计法即计算机内部进行执行时间和实际占用空间的统计。

    缺点:

    1 .必须运行依据该算法编制的程序

    2.所得时间的统计量依赖于计算机的硬件、软件等环境因素即不同计算机不同环境所得的时间不同。

2 . 事先估算法

    事先估算法即求出该算法的一个时间界限函数。

    决定因素:

  1. 依据的算法选用何种策略
  2. 问题的规模
  3. 书写程序的语言,对于同一个算法而言实现语言的级别越高,执行的效率就越低;
  4. 编译程序所产生机器代码质量
  5. 机器执行指令的速度

算法中基本操作重复执行的次数是问题规模n的某个函数,其时间量度记作 T(n)=O(f(n)),称作算法的渐近时间复杂度,简称时间复杂度

以下六种计算算法时间的多项式是最常用的。其关系为:

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

  • 指数时间的关系为:

O(2n)<O(n!)<O(nn)

例:

    两个n阶方阵的乘法

for(i=1,i<=n; ++i)

for(j=1; j<=n; ++j)

{ c[i][j]=0 ;

for(k=1; k<=n; ++k)

c[i][j]+=a[i][k]*b[k][j] ; }

由于是一个三重循环,每个循环从1到n,则c[i][j]+=a[i][k]*b[k][j]执行总次数为: n×n×n=n3 时间复杂度为T(n)=O(n3)

  评论这张
 
阅读(39)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017