2 m0126 m0126 于 2016.01.20 13:25 提问

数据结构 在线等。

在带头结点的单链表中,若被删除结点位置概率相等,则删除第i个结点的时间复杂度是?

5个回答

91program
91program   Ds   Rxr 2016.01.20 14:39

O(1)
单链表只需要改变指针赋值的几个基本操作就可以完成删除单个结点,所以是O(1)

devmiao
devmiao   Ds   Rxr 2016.01.20 13:28

O(n)
查找需要的时间是O(n),删除是O(1),所以是O(n)

cuiwei1026522829
cuiwei1026522829   Ds   Rxr 2016.01.20 13:33

O1,直接就能删除…

kevin_IoT
kevin_IoT   2016.01.20 15:41

时间复杂度是On,因为查找的时间复杂度是On,删除的时间复杂度是O1,所以删除一个单链表节点的时间复杂度还是On

wojiushiwo945you
wojiushiwo945you   Ds   Rxr 2016.01.20 13:27

在一个具有n个节点的单链表中删除第i个节点算法的时间复杂度是O(n);因最坏情况是删除最后一个结点,所以要找到最一个结点的前驱,也就要访问前n-1个结点,故算法的时间复杂度为O(n);

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!