天马行空

说明对于相同的逻辑结构,采用不同的存储方式会影响其操作效率

  • 2019-06-25 22:07:41
  • 237 次阅读
  • 稿源:天马行空

顺序表和链表都是线性表,这是他们的共同之处(逻辑结构相同),但它们的存储方式是不同的。那就看看在顺序表和链表中运算效率是怎样产生不同的?

线性表既可以采用顺序存储方式,也可以采用链式存储方式来实现。

(1)在顺序存储方式下,在线性表中插入和删除元素,平均要移动一半的元素,时间复杂度是O(n)。

事实上,就是在数组中进行增删操作。

例如:下面的数组存放了n个元素,若要在末尾插入一个元素,只要顺序表有足够的空间,就可以通过数组的下标号索引到数组的n+1个位置,直接将元素插入到里面,这只要花费O(1)的时间复杂就可以了。但是,这是一种特殊的情况。但若要在数组的头部插入元素一个元素,会影响到后面的元素,那么这些元素都会统一的依次往后面移动一个位置,给第一个位置要插入的元素空出一个单元格。这样会移动n个元素,消耗的时间复杂度为O(n)。同理,删除操作也便如此。

举例说明对于相同的逻辑结构,采用不同的存储方式会影响其操作执行效率

小结:顺序表插入和删除操作,在头部n次操作,在尾部一次操作,就平均而言,需要n/2次操作。

(2)在链式存储方式下,例如,在下面的单表中,链接了n个结点。在这里我们不考虑每次都要从头结点重新遍历一遍。譬如,要在单链表的末尾插入一个n+1结点,就是在找到N结点后,直接链接N+1这个结点,而不是重头找一遍。这个过程的时间复杂度为O(1)。同理,删除一个结点操作的时间复杂度也是O(1),直接把链接箭头断开就可以了。

For example, for the same logical structure, different storage methods can affect the efficiency of its operations 02

小结:单链表,插入和删除操作的时间复杂度为O(1)。在这里没有考虑查找这一过程。

喜欢 0

文章评论 (1)

  1. 挽救婚姻说道:

    感谢分享

    [1楼]网友 Windows 7 | Chrome 67.0.3396.99 回复   

表情

大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头