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

Question

我所知道的任何数据结构的顺序数据，最多有一个O(log n)查找

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

需要O(log n)时间

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

在任何情况下，似乎平均总时间复杂度必须是O(log n)。

这是正确的，还是我们能做得更好?

Answer 1

如果您的值被限制在一个合理的范围内，并且首先没有对构建数据结构的复杂性的限制，那么您可以通过使用经典的时间/空间权衡来在O(1)内完成。

简单地保持一个足够大的数组来容纳所有可能的输入值。用一个表示没有有效最大值的值初始化它。要插入一个新值，在上面的每个数组元素中填充该数值，直到到达已经包含不同最大值的元素为止。完成后，获取最大值就像获取数组索引处的值一样简单。

在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 2

不，没有更有效的基于比较的算法。使用基于比较的算法，最坏的情况确实是由Omega(logn)限定的，因为有n个可能的输出(给定正确的查询，所有输出都可以实现)，并且为了选择其中一个，计算树的高度必须为log(n)。这给了我们一个Omega(logn)的下界，对于这个问题使用比较，不管使用的数据结构。

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

Answer 3

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

Answer 4

回答一个更实际的问题:对于一个排序数组中的每一个x，求小于x的最大值。

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

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

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