o9fjrh1
2015-12-15 16:16
采纳率: 100%
浏览 7.2k
已采纳

数据结构,在一个双向链表中删除一个元素的时间复杂度怎么计算?

数据结构,在一个双向链表中删除一个元素的时间复杂度怎么计算?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • blownewbee 2015-12-15 16:16
    已采纳

    查找元素时间复杂度O(N),删除O(1),所以是O(N)

    点赞 评论
  • RapdoZoro 2015-12-16 00:57

    为了找到第i个结点,链表中需要从头结点开始一个一个向后查找,直到找到第i个结点为止,所以为了找到第i个结点,需要用i-1个程序步,因此,它们的时间复杂度是O(N),但删除该节点一次性就可以删除掉复杂度为O(1),所以总的时间复杂度为O(N)

    点赞 评论

相关推荐 更多相似问题