对两种线性表的时间和空间代价的分析

我们学习了两种实现线性表的方法,即顺序表以及链表.从以前学过的顺序表以及链表的实现中可以很简单的看出下面的几点:
对于顺序表的最大缺点是它的元素个数在创建对象时必须指定,那就是说我们不能因为需要更多的内存空间而在表后添加内存,也不可能因为只用几个元素而把用不着的内存释放.即
缺少灵活性.而在链表结构中,这种缺点是不存在的,因为链表可以根据所需内容增大或缩小节点数.

但是由于链表需要多余的内存来保存一些组成数据结构的成员,例如指向下一个元素的指针,从而内存占用空间代价在同相的节点(元素)来说比顺序表的要多.由其是实际保存的值所
占用的内存空间比较小的时候更是如此,例如以前我们学习的int型的链表来说.因为我们可用的值为int类型,占用4字节内存,而指针也占用了4字节内存.这样内存空间代价要高出一
倍,但是顺序表中的节点内存则是全部由我们有用的数值占用.
从上面可以看出,顺序表以及链表各有优点,那么我们在什么时候选择哪种数据结构更高较呢?下面我们引入几个参数来比较:
设n表示线性表中的元素个数.
设P表示指针的存储单元大小(一般为四字节).
设E表示数据元素的存储单元大小(可任意大小).
设D表示可以在数组中存储的线性表元素的最大数目.
那么链表的空间需求可以用下面的式子表示:
n(P+E)
而线性表可以表示为:
nE
从上面的两个式子可以看出,不管在任何情况下,顺序表的空间大小一定小于链表,而不管n的值为多少.但是这种情况我们忽略了最大元素D的值,那么我们再看一下如果元素个数刚好
为D时的空间占用情况:
链表为:D(P+E)
顺序表:DE
那么对于链表来说,n总是等于D,因为链表可以动态的升缩,只要内存足够多,那么可以创建任意个节点,但是对于顺序表来说,D跟n不一定总是相等,在这种情况下,有些顺序表的内存
是被浪费的.由其是n<=D/2的时候浪费的更多.
这么说,顺序表的空间占用情况跟n和D的值有关,那么我们给出一个n值的临界值n>DE/(P+E),当n超过这个值时在任何时候,顺序表的空间效率总是高于链表.如果P=E(例如我们用int
类型实现的链表),那么上面的式子就为n>D/2,即元素个数多于一半以上时,顺序表更有效率.
作为一般规律,当线性表元素数目变化较大或者未知时,最好便用链表实现,而如果用户事先知道线性表的大致长度,使用顺序表的空间效率会更高.诸如取出线性表中第i个元素这样
的按位置随机访问,使用顺序表更快一些;通过next和prev可以很容易调整当前位置向前或者向后,相比之下,单向链表不能直接访问前面的元素,按位置访问只能从表头开始,直到找
到那个特定的位置.这样会花费更长的时间.给出指向链表中合适位置的指针后,insert和remove函数所需的时间是一个常数,因为只用经过一个步骤就可以完成,而顺序表必须在数组
内将其余的元素向前或向后移动.这种方法所需要的平均时间由要移动的元素个数所决定.对于许多应用,插入和删除是最主要的操作,因此它们的时间效率是举足轻重的.仅就这个原
因而言,链表往往比顺序表更好.
至于要使用顺序表还是链表,我们只有在分析要解决的问题时选择,例如要经常改变元素个数,而且元素个数不确定和频繁插入以及删除元素时,链表是一个很好的选择.而元素个数已
知或者没有太大的改变以及频繁得到元素的值时,顺序表比链表更高效.
下面分析一个很重要的问题:元素的表示.
在创建上面的数据结构时,对于保存节点的数据,我们不得不考虑下面的几个问题:
1.元素中的成员是保存数值还是保存一个指针.即我们在C++中学习的深复制还是浅复制问题.如果是保存一个指针,那么数值实际上是在另一个地方被保存,那么两个指针进行赋值操
作时,两个指针都指向同一个内存单元,那么应用一个指针改变保存的数值时,有可能会影响另一个指针,甚至会使该指针指向无效的内存单元,而元素中保存值却没有这个问题.这是
我们要考虑的第一个问题.
2.每个元素中保存的是相同数据类型的值吗?如果我们要保证元素中的数据类型的相同,那么用什么方法保证?
这个问题在顺序表中不太可能发生,因为顺序表实际上是一种数据类型的数组,而数组的任何元素类型是相同的,但是在链表的数据结构中却可以实现每一个节点中保存的数据都不相
同,所以我们在使用时要判断元素中的数据类型需要相同吗?而如果用户提供了不同类型的数值要求保存入链表节点中时我们要怎么样保证节点数据类型的一致性?这些都是我们要考
虑的问题.
3.当线性表中的元素(节点)被删除或调用Clear函数时,存储在该表中的对象占用的内存将被如何处理.
这一点我们在"对new和delet操作符的一点想法"这篇文章中作了比较详细的分析,在此我们不再说明.

本文来源 我爱IT技术网 http://www.52ij.com/jishu/1762.html 转载请保留链接。