试谈数据结构研究(doc 16页)
所属分类：数据仓
文件大小：500 KB
下载要求：10 学币或VIP
点击下载
资料简介：
试谈数据结构研究内容提要：
链式结构的优缺点
链式存储结构是采取连表指针来指示数据的存储位置,这就可以是在内存中随意的存储,没有必须连续储存空间的要求,对于内存的要求相对教容易.但是要是是从小到大顺序排列的数据,链式存储结构的时间复杂度教小,效率高.但是要是不规则排布的数据一般时间复杂度较高,效率更低
算法渐进复杂度的表示方法
算法时间复杂度的渐进分析：在时间复杂度t(n)中，剔除不会从实质上改变函数数量级的项，经过这样处理得到的函数是t(n)的近似效率值，但这个近似值与原函数已经足够接近，当问题规模很大时尤其如此。这种效率的度量就称为算法的渐进复杂度。(在不引起混淆的情况下，也可简称时间复杂度)
算法的最好、最坏和平均时间复杂度
算法的复杂度往往取决于输入数据，例如一个排序算法的时间复杂度往往取决于输入数据的原始有序程度。因此分析算法复杂度时往往要区分最好情况、最坏情况和平均情况。
例如，在一个包含n个元素的数组中查找某个数据(假定该数据是数组元素)：
最好情况：该数据就是第0个元素，只需比较1次就可以结束了，其复杂度为O(1)。
最坏情况：该数据是数组最后一个元素，则需要比较n次，其复杂度为O(n) 。
评均情况：假设需要查找的数据是第0个元素、第1个元素、…、最后一个元素的概率相等，则平均需要查找的次数为：1×1/n + 2×1/n + … + n×1/n = (n+1)/2。其复杂度为O(n)。
..............................
精品资料网 m.cnshu.cn
Copyright © 2004- 粤ICP备10098620号-1
