O(n) deque version is slow than o(nk) array version in python suggests optimise constants in time complexity useless?


  • 0
    Z
    from collections import deque
    class Solution(object):
        def maxSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[int]
            """
            n = len(nums)
            if n <= 1:
                return nums
            q=deque([])
            r=[]
            for i in range(n):
                e = nums[i]
                while len(q)>0 and e>=q[-1][1]:
                    q.pop()
                q.append((i,e))
                
                if q[0][0]<i-k+1:
                    q.popleft()
                if i>=k-1 :
                    r.append(q[0][1])
            return r
    

    this version runs slower than the ordinary o(nk) comparison. 220ms versus 180ms which I guess relates to the deque implementation and the tuple involved.

    my understanding is optimised the constants k in time complexity requires extra caution in small scale data. because overhead occurred elsewhere could easily cost you what you saved.


  • 0
    T

    I agree, I think these timings just mean that the test cases test for validity, but not for asymptotic performance. For small k also iteration may be faster than memory access elsewhere (deque).


Log in to reply
 

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