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

  • 0
    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
            for i in range(n):
                e = nums[i]
                while len(q)>0 and e>=q[-1][1]:
                if q[0][0]<i-k+1:
                if i>=k-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

    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.