首页 > 试题广场 >

在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作

[单选题]

在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是（）:

访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)

在第i个结点后插入一个新结点(1≤i≤n)

查看答案及解析

wanye_z

表分为顺序表和链表。

A、顺序表的特点就是随即存取，所以访问节点的时间复杂度为O(1)。

B、插入一个节点，那么这个节点之后的所有节点都分别要向后移动一个，所以时间复杂度为O(n)。

C、同样，删除一个节点，那么后面的所有节点都需要向掐移动一个，所以时间复杂度为O(n)。

D、排序。。常见的排序方法中最快的也是O(n)，即使是桶排序，也是不可能达到O(1)的。

所以这道题选A。

发表于 2017-09-08 23:51:44 回复(2)

提交观点

问题信息

复杂度

上传者：星辰大海的碎片

难度：

1条回答 107收藏 23586浏览

扫一扫，把题目装进口袋