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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
数据结构 算法 在线演示
http://sjjg.js.zwu.edu.cn/SFXX/sf1/sfys.html
最大子列和(递归、在线处理)——浙大数据结构(陈越)
public class Test1 { public static void main(String[] args) { // TODO Auto-generated method stub int[] a ={-1,3,-2,4,-6,1,6,-1,-3,4,1,-4,6,2,-4,5}; System.out.println(maxSum1(a)); System.out
学堂在线-数据结构-PA1-范围查询(Range)-解题报告
问题描述 数轴上有n个点,对于任一闭区间 [a, b],试计算落在其内的点数。 输入 第一行包括两个整数:点的总数n,查询的次数m。 第二行包含n个数,为各个点的坐标。 以下m行,各包含两个整数:查询区间的左、右边界a和b。 输出 对每次查询,输出落在闭区间[a, b]内点的个数。 样例 5 2 1 3 7 9 11 4 6 7 12
数据结构总复习
核心要点–必须掌握 掌握数据结构的基本概念和术语。包括:数据,数据元素,数据项,数据结构等基本概念 算法和算法分析:掌握算法,算法的时间复杂度和空间复杂度,掌握算法分析的方法,对一般算法能分析处时间复杂度。还有算法的特性。 掌握线性表的定义和逻辑结构,了解线性表的基本运算, 掌握顺序表的插入和删除操作及平均时间性能分析 熟练掌握单链表,插入和删除操作并分析其时间复杂度 了解循环单链表算法和单链表上相
数据结构与算法:最短路径,拓扑排序的基本概念
“相较于其它方式,我一直热衷于推崇围绕数据设计代码,我想这也是Git能够如此成功的一大原因[…]在我看来,区别程序员优劣的一大标准就在于他是否认为自己设计的代码还是数据结构更为重要。” —— Linus Torvalds “优秀的数据结构与简陋的代码组合远比反之的组合更好。” —— Eric S. Raymond, The Cathedral and The Bazaar 学习
数据结构学习(十)——串的操作
几天没看数据结构了,今天重新开始了。     串是一种特殊的线性表,它的每个结点是一个字符,所以串也称作字符串。     关于串的操作主要有求串长,串复制,串连接,求子串,串插入,串删除,子串定位等。串的操作也是C语言笔试中常考的一部分。     下面的代码实现了串的主要操作。 #include #include #define MAXSIZE 20 char *String_C
在线用户列表数据结构设计
每次说起自己项目里面涉及到的数据结构时,总是说得稀里糊涂的,完全表达不清楚。今天尝试着写出来,顺便理清楚自己的思路。         我之前是在做一个基于web的接入认证和控制系统,其中包括了对用户在线时长统计的功能需求。在web认证的流程里,用户经过认证之后,用户的浏览器仍然需要向认证服务器发送心跳请求,通知服务器该用户仍然在线。当在一定的间隔内,没有收到用户的心跳请求时,就认为该用户已经异常
代码在线练习平台
在线练习平台
《数据结构》第01章在线测试
《数据结构》第01章在线测试 剩余时间:  答题须知:1、本卷满分20分。            2、答完题后,请一定要单击下面的“交卷”按钮交卷,否则无法记录本试卷的成绩。            3、在交卷之前,不要刷新本网页,否则你的答题结果将会被清空。 错误列表: 1.4 2.3 2.5 第一题、单项选择题(每题1分,5道题共5分)  1、在线性结构中,除最后一个
在线数学函数图形和在线数据结构演示
Desmos Graphing Calculator https://www.desmos.com/calculator HTML5数学函数图形绘制插件XCalc http://www.html5tricks.com/demo/html5-xcalc-demo/index.html