顺序算法的复杂性 - 最小后缀

Question

在顺序算法(非并行)..

在数组的每个后缀中找到min的最佳复杂度是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}

Answer 1

用这个事实

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