在顺序表上实现比在链表上实现效率更高的是哪一种

[问答题]

对于长度为n的线性表，下面给出的4种操作中，在顺序表上实现比在链表上实现效率更高的是哪一种？请分别用大O符号表示的时间复杂度形式说明你的理由。

（1）输出线性表中第i个数据元素的值（1 ≤ i ≤ n）；

（2）交换线性表中第1个数据元素与第2个数据元素的值；

（3）依次输出线性表的n个数据元素；

（4）输出线性表中与给定值x相匹配的数据元素在线性表中的序号。

郭新鹏

（1）输出线性表中第i个数据元素的值（1 ≤ i ≤ n）；

在顺序表中时间复杂度为O(n)，在链表中时间复杂度为O(n)

理由：都是从头开始遍历，找到第i个元素

（2）交换线性表中第1个数据元素与第2个数据元素的值；

在顺序表中时间复杂度为O(n)，在链表中时间复杂度为O(1)

理由：顺序表中交换顺序，需要移动内存。而在链表中只需要交换指针即可。

（3）依次输出线性表的n个数据元素；

在顺序表中时间复杂度为O(n)，在链表中时间复杂度为O(n)

理由：都是从头开始遍历，遍历每个元素

（4）输出线性表中与给定值x相匹配的数据元素在线性表中的序号。

在顺序表中时间复杂度为O(n)，在链表中时间复杂度根据算法来确定，可以从头遍历O(n)，可使用折半查找法遍历O(logn)

如有误，欢迎讨论

编辑于 2017-10-16 14:33:54 回复(2)

提交观点

问题信息

数组链表

上传者：城市里的养猫者

难度：

1条回答 9收藏 7335浏览

扫一扫，把题目装进口袋