问答

当前位置

98.Sort List 时间复杂度

  • Ta: 衡助教

这道题的找中点的那一步的时间复杂度是O(n), 是怎么算进整个答案的O(nlogn)的时间复杂度里面的呢?在这个地方脑子有点转不过来。

我用的是归并排序的解法。我是这样理解的:
1.先遍历链表一遍找出中点,用时O(n),这里n为当前子链表的长度,可能小于原链表的总结点数,但是因为每层递归一共都要遍历整个链表,所以这里用链表总长度n来表示是合理的(比如第一层递归要找两次中结点,每次遍历的子链表长度n/2;第二层递归要找4次中结点,每次遍历的子链表长度n/4;所以每层一共遍历了n个结点;以此类推);
2.接下来这个算法通过递归调用分别算出左半边和右半边排好序的子链表的头结点,递归次/层数是O(logn)
3.然后在每层的递归的时候,每段子链表除了要找中点,还要排序,每层一共要排n个结点(但是每次递归调用需要排的结点数只是当前logn层里某一层需要处理的结点数,是小于n的)。但是按层计算的话排序就是用时O(n)

合起来看的话,一共logn层递归,每层消耗O(n)时间找中点加上O(n)的时间排序,2n即是O(n)。所以总体是O(nlogn)。这样理解没问题?

1 个回复

2019-09-17 carry

没问题,就是这样算的归并的时间fu'za'du

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1