在单链表中删除一个指定节点的后继的时间复杂度是多少?
1个回答
2022-09-28 · 百度认证:北京惠企网络技术有限公司官方账号
关注
展开全部
时间复杂度是O(n)
在一个具有n个节点的单链表中删除第i个节点算法的时间复杂度是o(n);因最坏情况是删除最后一个结点,所以要找到最一个结点的前驱,也就要访问前n-1个结点,故算法的时间复杂度为o(n)。
for(i=1;i<n;i++);// 由于这里有一个分号,所以执行n次
for(j=1;j<i;j++)// 此时i=n,所以执行n次。
共执行2n次,时间复杂度是O(n)。
扩展资料:
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
参考资料来源:百度百科-时间复杂性
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询