线性表顺序存储的优缺点

插入与删除的时间复杂度
服务器君一共花费了218.770 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

插入和删除的时间复杂度

先来看最好的情况,如果元素要插入到最后一个位置,或者删除最后一个元素, 此时时间复杂度为0(1),因为不需要移动元素的,就如同来了一个新人要正常排队,当然是排在最后,如果此时他又不想排了,那么他一个人离开就好了,不影响任何人。

  • 最坏的情况呢,如果元素要插入到第一个位置或者删除第一个元素,此时时间复杂度是多少呢?那就意味着要移动所有的元素向后或者向前,函数要对线性表循环一遍操作,所以这个时间复杂度为 0(n)。

至于平均的情况,由于元素插入到第i个位置,或删除第i个元素,需要移动n—i个元素。根据概率原理,每个位置插入或删除元素的可能性是相同的,也就说位置靠前,移动元素多,位置靠后,移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等,为(n-1)/2

  • 我们前面讨论过时间复杂度的推导,可以得出,平均时间复杂度还是 0(n)

这说明什么?线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是0(1);而插入或删除时,时间复杂度都是0(n)。这就说明,它比较适合元素个数不太变化,而更多是存取数据的应用。当然,它的优缺点还不只这些……

线性表顺序存储结构的优缺点

从优点开始说。当我们在使用线性表的时候,我们不需要为表中元素之间的逻辑关系而增加额外的存储空间,而且可以快速的存取表中任意位置的元素。接下来谈谈缺点。如我们所见,如果我们要插入或者删除的元素是在第一个位置,那么无疑的,我们需要移动大量的元素来完成这样的操作,而且限于线性表长度必须小于数组长度,如果我们需要插入大量数据,那么很难保证空间是否充足,而如果我们要删除大量数据的时候,无疑又会造成空间的浪费。

优点:

具有简单、运算方便等优点,特别是对于小线性表或长度固定的线性表,采用顺序存储结构的优越性更为突出;

缺点:

  1. 顺序存储插入与删除一个元素,必须移动大了的数据元素,以此对大的线性表,特别是在元素的插入和删除很频繁的情况下,采取顺序存储很是不方便,效率低;
  2. 顺序存储空间容易满,出现上溢,程序访问容易出问题,顺序存储结构下,存储空间不便扩充;
  3. 顺序存储空间的分配问题,分多了浪费,分少了空间不足上溢。

延伸阅读

此文章所在专题列表如下:

  1. 第01话:线性表的概念与定义
  2. 第02话:线性表的抽象数据类型ADT定义
  3. 第03话:线性表的顺序存储结构
  4. 第04话:线性表的初始化
  5. 第05话:线性表的遍历、插入操作
  6. 第06话:判断线性表是否为空与置空操作
  7. 第07话:线性表的查找操作
  8. 第08话:线性表删除某个元素
  9. 线性表顺序存储的优缺点
  10. 线性表链式存储结构的由来与基本概念
  11. 单链表的头指针、头结点与首元结点
  12. 单链表的结构体定义与声明
  13. 单链表的初始化
  14. 单链表的插入与遍历操作
  15. 单链表的删除某个元素的操作
  16. 获取单链表中的指定位置的元素
  17. 查找某数在单链表中的位置
  18. 用头插法实现单链表整表创建
  19. 用尾插法实现单链表整表创建
  20. 将单链表重置为空表
  21. 单链表反转/逆序的两种方法
  22. 单链表反转/逆序的第三种方法
  23. 求单链表倒数第N个数
  24. 用标尺法快速找到单链表的中间结点
  25. 如何判断链表是否有环的存在
  26. 单链表建环,无环链表变有环
  27. 删除单链表中的重复元素

本文地址:http://www.nowamagic.net/librarys/veda/detail/2208,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2208

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《高性能网站建设指南》 桑德斯 (Steve Sounders) (作者), 刘彦博 (译者)

《高性能网站建设指南》结合Web2.0以来Web开发领域的最新形势和特点,介绍了网站性能问题的现状、产生的原因,以及改善或解决性能问题的原则、技术技巧和最佳实践。重点关注网页的行为特征,阐释优化Ajax、CSS、JavaScript、Flash和图片处理等要素的技术,全面涵盖浏览器端性能问题的方方面面。在《高性能网站建设指南》中,作者给出了14条具体的优化原则,每一条原则都配以范例佐证,并提供了在线支持。全书内容丰富,主要包括减少HTTP请求、ExpiresHeader技术、Gzip组件、CSS和JavaScript最佳实践、关闭ETags的技巧、Ajax缓存技术和最小化技术等。

更多计算机宝库...