在整数列表中找到 'pits'。快速地

Question

我正在尝试编写一个程序，在列表中找到“pits” 整数。

A pit is any integer x where x is less than or equal to the integers immediately preceding and following it. If the integer is at the start or end of the list it is only compared on the inward side.

For example in: 
    [2,1,3] 1 is a pit.
    [1,1,1] all elements are pits.
    [4,3,4,3,4] the elements at 1 and 3 are pits.

我知道如何通过采取线性方法并向前走来解决这个问题列表但是我很好奇如何应用分而治之
相对快速地做到这一点的技术。我很缺乏经验而且我不太确定从哪里开始，我觉得类似于二进制文件可以应用树吗？

如果相关的话，我在 Python 3 工作。感谢您的宝贵时间 :).

Answer 1

如果没有关于列表中值分布的任何附加信息，则不可能实现小于 O(x) 的任何算法复杂度，其中 x 是列表中元素的数量。

从逻辑上讲，如果数据集是随机的，例如布朗噪声，则坑可能发生在任何地方，需要完整的 1:1 采样频率才能正确找到每个坑。

即使只是想找到序列中绝对最低的坑，在不影响结果正确性的情况下，也无法在亚线性时间内实现。

可以考虑优化，比如单纯的并行化或者跳坑附近的值，但是整体的复杂度还是一样的。

在整数列表中找到 'pits'。快速地

Find the 'pits' in a list of integers. Fast

python

performance

divide-and-conquer