我要招人

去企业版

首页 > 试题广场 >

对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为（

[单选题]

对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为（）

```
O(n)
```
```
O(1)
```
```
O(n^2)
```
```
O(nlog2n)
```

查看正确选项

KatherineYang

每次都是从头扫描链表，找到表尾，扫描次数为1,2,3,4，.....,n-1

发表于 2017-06-01 20:32:02 回复(0)

心系蝶相印

很迷，在一维数组倒序，链表正序的情况下，如

int a[5] = {5,4,3,2,1}

生成链表，且使用头插法，时间复杂度为O（1*n）

1->2->3->4->5

此种应该是最低的吧

发表于 2018-09-10 21:34:14 回复(1)

mylyt

我用一个数组来存储链表元素，然后用插入排序排元素，再顺序放入链表，不可以是O(n^2)吗

发表于 2019-09-02 07:56:17 回复(0)

墨麟非攻

总的时间复杂度为O(nlogn)+O(n)=O(nlog2n)

nlog₂n + n = nlog₂n + nlog₂2 = nlog₂(2n)

故时间复杂度为O(nlog2n)

发表于 2019-07-03 11:44:17 回复(0)

sou

建表是O（n）,但排序的时间复杂度不确定，

发表于 2018-03-07 19:12:41 回复(0)

孙健-字节跳动

应该是先排序，在构建链表，排序是O(nlogn)，构建链表是O(n)

总的时间复杂度为O(nlogn)+O(n)=O(nlog2n)

发表于 2017-06-02 11:45:38 回复(7)

Qiadle

排序算法的时间复杂度不一定为O(nlgn),比如桶排序……

发表于 2019-05-20 20:36:48 回复(0)

佩恩六道

没说平均，最好，最坏情况，呵呵。

发表于 2019-02-23 14:05:53 回复(0)

我的欧肥儿在哪里

千万不要忘记算排序的时间复杂度

发表于 2019-02-18 01:08:37 回复(0)

learner111111

我想可能是模拟归并排序或者折半插入排序的过程去建有序单链表吧。这样子应该是最快的建表过程，时间复杂度为nlog(n)。

发表于 2018-10-25 17:21:57 回复(0)

avasdf

说的是构建表的复杂度不是排序的复杂度

发表于 2018-08-18 09:08:22 回复(0)

NB响当当

难道不能在重新建表的时候多设一个指针指到插入指针的前面，然后利用插入排序的方法进行插入排序吗？你有没有问最快，O(n²)完全没毛病吧

发表于 2018-04-04 13:03:45 回复(2)

孤单的跟鞋声和你的笑丶

排序那里的话，如果是快速排序那么是o(nlogn)但是也不一定是快排的说，题目也不是很明确，快排，堆排这个倒是没毛病，构建表是o(n)。

编辑于 2017-12-09 16:14:22 回复(0)

Evildoer灬黎

就是感觉这题怪怪的。。。

发表于 2017-08-29 19:44:58 回复(1)

我的世界(◔◡◔)

这题，，，要看用什么方法怎么创建的吧。。

发表于 2017-08-28 18:13:02 回复(0)

呼啦啦要瘦瘦

构建链表是O(n^2),我认为这道题目应该选C

发表于 2017-08-11 22:16:47 回复(0)

sgbs

正确答案到底是啥？

发表于 2017-06-04 08:45:47 回复(0)

提交观点

问题信息

链表复杂度

上传者：齐小乐

难度：

17条回答 451收藏 17548浏览

对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为（

问题信息

热门推荐

相关试题