时间戳

首页 > 解决方案 > how can i write this algorithm more efficiently ? in a way that reduce time complexity?

arrays - how can i write this algorithm more efficiently ? in a way that reduce time complexity?

问题描述

So I write this code and I wanted to reduce time complexity of it but am not sure how, so what is the best way to write a more efficient algorithm so I can reduce time complexity, the code subtract from each element the first small number after it for example if the array is [1, 5, 6, 3, 2] then the result is [1, 2, 3, 1, 2].

# an array with numbers
arr = [1, 5, 6, 3, 2]
# outer loop picks all element one by one
for i in range(0, len(arr), 1):
    Next = arr[i]
    # inner loop looks for the next smaller element
    for j in range(i + 1, len(arr), 1):
        if arr[i] > arr[j]:
            # if the condition is true, the element will be subtracted form the next smaller element
            # if there was no next smaller element, the element will kept without change
            Next = arr[i] - arr[j]
            break
    print(Next)

标签： arraysalgorithmloopselement

解决方案

Indeed, your solution has O(n²) time complexity. You can improve on that.

Start from the end of the list and walk backwards.

While doing so, push an inspected list value on a stack when it is not less than the value currently on the top of the stack. At the same time output the difference.

When, on the other hand, an inspected value is less than the value on the top of the stack, then pop the stack until the value on the input value is no longer less than the value on top of the stack, and do again as described in the previous paragraph.

Here is an implementation of that idea:

def solve(arr):
    stack = [0]
    result = arr[:]
    # outer loop picks all element one by one
    for i in range(len(arr) - 1, -1, -1):
        val = arr[i]
        while val <= stack[-1]:
            stack.pop()
        result[i] = val - stack[-1]
        stack.append(val)
    return result

Call this function as follows:

arr = [1, 5, 6, 3, 2]
print (solve(arr))   # [1, 2, 3, 1, 2]

This algorithm has a linear time time complexity: O(n). Although the inner while loop looks suspicious of a non-linear time complexity, it still is, because a given list value will at most be pushed and pulled only once on/off the stack.

推荐阅读