Confusion about time complexity of 2 approaches.


  • 0
    Y
        def mergeKLists(self, lists):
        lists = [list for list in lists if list]
        if not lists:
            return None
            
        lis = []
        for head in lists:
            while head is not None:
                lis.append(head.val)
                head = head.next
        lis.sort()
        
        dummyHead = ListNode(0)
        p = dummyHead
        for val in lis:
            p.next = ListNode(val)
            p = p.next
        return dummyHead.next
    

    I think the time complexity of above solution is O(nk log(nk)). Since sort( ) takes O(nlog(n)) time according to https://wiki.python.org/moin/TimeComplexity
    And this solution actually takes 136ms.

    While the divide and conquer approach as following:

    `def mergeKLists(self, lists):
            lists = [list for list in lists if list]
            if not lists:
                return None
            end = len(lists) - 1
            while end > 0:
                begin = 0
                while begin < end:
                    lists[begin] = self.merge(lists[begin], lists[end])
                    begin += 1
                    end -= 1
            return lists[0]
            
        def merge(self, lis1, lis2):
            dummyHead = ListNode(0)
            p = dummyHead
                
            while lis1 and lis2:
                if lis1.val < lis2.val:
                    p.next = lis1
                    p = p.next
                    lis1 = lis1.next
                else:
                    p.next = lis2
                    p, lis2 = p.next, lis2.next
            if lis1: p.next = lis1
            if lis2: p.next = lis2
            return dummyHead.next`
    

    should be O(nk log(k)), actually takes 504ms.

    I'm confused about the time efficiency comparison, why the first solution is way faster than the second solution when its time complexity is larger?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.