已知两个长度分别为m 和 n 的升序链表,合并降序链表,求时间复杂度 |
您所在的位置:网站首页 › n的时间复杂度 › 已知两个长度分别为m 和 n 的升序链表,合并降序链表,求时间复杂度 |
王道数据结构上一道题:
之前我看到一个电子版的书,上边答案解析写的有点错误, 听说有些同学买的实体书上,答案解析也是这样写的 这个是刊印错误,很显然2Max( m , n )大于等于 m + n 而且这个解析也不够清晰。 解析:选D两个升序合并为降序,操作就不多说了,两数列依次比较放入,其中一个数列结束了,剩下的就不用比了,直接依次放进去。 首先明确,题目让我们求复杂度,这里显然不是讨论移动次数,因为不论什么情况,移动次数都是(M+N),不需要讨论 所以这里求的是合并过程中的比较次数 最好的情况,很容易想,就是长度较短的数列中最小的数还比另一个数列最大的数字大,如(7 8 9和 1 2 3 4 ),这种情况需要比较min(m,n)次就好了,复杂度为O(min(m,n))。 最差的情况,什么是最差情况,就是比较的次数最多。怎么算呢,要这样想,两个数列移动元素的次数一定是m+n,不可能比这个还多,那么如果每一次移动都需要比较,岂不就是最差情况?但是注意,最后一次移动是一定不需要比较的,因为剩最后一个元素的时候,必然另一个数列已经结束了,所以不用比。故最坏情况比较次数为(m+n-1) 次 给几个例子试试:1 3 5 7 9 和 2 4 6 8 10 / 1 3 5 和 2 4 那么,题目要求最坏情况复杂度,就是O(m+n-1)咯 可是选项没有,哈哈,别急,比较次数是 (m+n-1) 次,m和n的次幂都是1,所以复杂度也是一次就行了,那么到底是O(n)还是O(m)呢,肯定选最大的那个啊,因为是最坏情况,故复杂度为O(Max(m,n)) -------------------------------------------------------------------------------------------------------------------------------
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |