complexity-theory - 顺序算法的复杂度-最小后缀

在顺序算法(非并行)中。

在数组的每个后缀中找到最小值的最佳复杂度是O(nlogn)还是O(n)？如果不？为什么？

INPUT:
array={x1,x2....xn}

OUTPUT:
X= {min(x1,x2....xn),min(x2....xn),(x3,x4....xn)...........min(xn-1,xn),xn}

最佳答案

使用事实

min(x1,x2,...,xn) = min(x1,min(x2,x3,...,xn))

您会看到可以使用DP算法来解决X中的O(n)
伪码

Min-Suffixes(input)
    n = input.length
    let output = new array of size n
    output[n] = input[n]
    for i = n-1 to 1
        output[i] = min(output[i+1],input[i])
    return output

关于complexity-theory - 顺序算法的复杂度-最小后缀，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22644138/