找到小于给定值的最大值的时间复杂度是多少？

Question

我所知道的任何排序数据的数据结构最多只能进行 O(log n) 查找。

我认为要找到小于给定值的最大值，我们需要首先发现给定值在数据结构中的位置。（我没有证据表明这是必需的第一步）。

这需要 O(log n) 时间。

从那里，我们需要找到小于该值的最大值。在数组的情况下，我们向后看一个索引 O(1)。在平衡树的情况下，我们遍历的路径通常为 O(log n)。

无论如何，平均总时间复杂度似乎必须是O(log n)。

这是正确的，还是我们能以某种方式做得更好？

Answer 1

不，没有更有效的基于比较的算法。最坏的情况确实受到 Omega(logn) 使用基于比较的算法的限制，因为有 n 可能的输出（所有这些都可以在给定正确查询的情况下实现），并且要选择其中之一，计算树必须是身高 log(n)。对于这个问题，无论使用何种数据结构，这都为我们提供了 Omega(logn) 的下限。

这个界限显然很紧，因为在排序数组中，可以使用二进制搜索在 O(logn) 中找到所需的值。

Answer 2

如果你的值被限制在一个合理的范围内，并且首先对构建数据结构的复杂性没有限制，你可以使用经典的 [=21= 在 O(1) 中完成]权衡。

只需为所有可能的输入值保留一个足够大的数组。使用指示没有有效最大值的值对其进行初始化。要插入新值，请用该数字填充 above 的每个数组元素，直到到达已包含不同最大值的元素为止。完成后，获取最大值就像获取数组索引处的值一样简单。

在Python中，对于任何值0到n_max：

array = [None] * (n_max + 1)
for n in values:
    for i in range(n + 1, n_max + 1):
        if array[i] == i - 1: break
        array[i] = n

for n in lookups:
    print array[n]

Answer 3

为了快速回答，是的，它必须是 O(logn)，因为您需要数据的顺序才能将您的值与数据进行比较，并看到确实没有其他东西比您的值更接近和低于您的值答案。

Answer 4

回答一个更实际的问题：为排序数组中的每个 x 找到小于 x 的最大值。

假设最大值集合的大小为 n，而要查找的 x 数组的大小为 m。

分别优化每个子问题，即迭代 x O(m) 次搜索值 O(logn)，你能做的最好的是 O(m*logn).

但是这个实际问题可以在 O(m+n) 中解决 - 如果两个数组都已经排序，这只是同时迭代两个数组的问题。显然只有 m > n 和常量才有意义对于特定尺码，因素可能更重要。

找到小于给定值的最大值的时间复杂度是多少？

What is the time complexity for finding the maximum value less than a given value?

algorithm

time-complexity