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

SINOBANJO

IN GOD WE TRUST ! ~ ClueeZhuo

 
 
 
 
 

日志

 
 

SINOBANJO---数据结构概率  

2014-06-30 02:21:16|  分类: 班卓数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

         数据结构是计算机组织数据存储数据的方式。

计算机解决一个具体问题时,一般需要经过以下几个步骤:

(1)       从具体的问题抽象出一个适当的数据模型;

(2)       设计一个求解该数学模型的算法;

(3)       用某种计算机语言编写实现该算法的程序,调试和运行程序直至最终得到问题的解答;

综上每个步骤数据的表现形式都是不相同的,实际问题中的数据称为原始数据。在数学

模型中,需要把原始数据按照某种方式组织起来,以便很好的提现数据之间的关系,数据以及数据的组成方式称之为数据的逻辑结构。为了能用计算机加工处理,逻辑机构还必须转换为能被计算机存储的存储结构。

在数据的逻辑结构中,根据元素之间关系的不同特点,通常有集合、线性结构、树形结构、图结构等四类基本,他们反映了四类基本的数据组成形式;在数据的存储结构中,一般包含两部分:存储数据元素、数据元素之间的关联方式 。在表示数据的关联方式时主要有顺序存储(所有的存储结点放在一个连续的存储区里。利用结点在存储其中的相对位置来表示数据元素之间的逻辑关系)、链式存储方式(每个存储结点除了含有一个数据元素外,还包含指针,每个指针指向一个与本结点有逻辑关系的结点,用指针表示数据元素之间的逻辑关系),除此之外还有索引存储方式散列存储方式。

一个问题可以有多种不同的求解算法,这样就产生了不同的算法。算法的时空性是指算法的时间性能(或时间效率)和空间性能(或空间效率)

         时间复杂度:

假设问题的输入规模为n,一般情况下,一个算法的计算量是问题规模n的函数。不考虑具体的运行时间,只给出算法在问题规模n下执行时间的上界,用大O渐进表示法:T(n)=O(f(n)) 称为算法渐进时间复杂度,简称时间复杂度。

         空间复杂度:

存储量和空间复杂度的概念与计算量和时间复杂度的概念类似,一个算法的空间复杂度定义为该算法所消耗的存储空间,它也是问题规模n的函数。S(n)=O(g(n)) 其中g(n)为问题规模n的某个函数。

         算法设计:

(1)       在整型数组A[n]中查找值为K的元素,若找到,则输出其位置i(0in-1),否则输出-1作为标致,分析算法复杂度。

SINOBANJO---数据结构概率 - 班卓 - BanjoElena—班卓伊莲娜国际

 

Figure 1-Arithmetic-Search

         当查找成功时,A[i]k比较次数小于等于n;当查找不成功时,A[i]k比较n次,所以算法时间复杂度T(n)=O(n)

(2)       分析方阵A[N][N]B[n][n]的乘积C[n][n]时间复杂度。

SINOBANJO---数据结构概率 - 班卓 - BanjoElena—班卓伊莲娜国际

 

Figure 2-Arithmetic-Matrix

         以方阵阶数n作为输入规模。在第二层循环中第一条赋值语句共执行n?次,第三层循环体中的乘法和赋值语句共执行n?,故算法的计算量为n?+n?,算法复杂度T(n)=O(n?)

 

(3)       读入n=100个整数到一个数组中,写出实现将该数组进行逆置算法,分析其空间复杂度。

SINOBANJO---数据结构概率 - 班卓 - BanjoElena—班卓伊莲娜国际

 

Figure 3-Arithmetic-S

         f1所需要的辅助变量为2个整型变量itemp,与问题规模无关,其空间复杂度为O(1).f2所需要的辅助变量为1个整型变量i和大小为n=100的整形数组b(与问题的规模无关),器空间复杂度为O(n)

         Thx.

  评论这张
 
阅读(133)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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