数组和链表的时间复杂度比较

lihang29 · 发表于 2014-4-1 15:17:05

您需要登录才可以下载或查看，没有账号？立即注册

x

数组和链表的插入操作的时间复杂度都是O（n），但是却说链表插入优于数组，这是为什么？
是不是因为链表每一次的操作量小于数组（不断赋值）吗？

～风介～ · 发表于 2014-4-1 16:30:13

{:1_1:}亲，可不可以这样理解: 数组每插入一个元素，考虑最坏的情况（即在第一个节点插入），则每个原先的元素都要往后移动一个位置；而链表插入一个元素，不需要移动原先的元素。所以说链表优于数组！

lihang29 · 发表于 2014-4-1 21:49:22

本帖最后由 lihang29 于 2014-4-1 21:51 编辑

～风介～发表于 2014-4-1 16:30

登录/注册后可看大图

亲，可不可以这样理解: 数组每插入一个元素，考虑最坏的情况（即在第一个节点插入），则每个原先的元 ...

链表虽然不需要移动，但是链表需要进行查找元素。。。。他们的时间复杂度都是O（N）

lihang29 · 发表于 2014-4-1 21:54:42

我在数据结构和算法的试音中看到这么一句话：当需要一次性插入大量数据的时候，使用元素的时间复杂度每一次都是O（N），但是对于链表除了第一次是O（N），后面的插入都是O（1）。所以说在对插入和删除操作使用较多的时候，链表优于数组。。{:1_1:}

～风介～ · 发表于 2014-4-1 22:08:16

lihang29 发表于 2014-4-1 21:54

登录/注册后可看大图

我在数据结构和算法的试音中看到这么一句话：当需要一次性插入大量数据的时候，使用元素的时间复杂度每一次 ...

{:1_1:}感觉这东西是正解！

账号		自动登录	找回密码
密码			立即注册