以下算法的计算复杂度？

Question

我有一个大小为 n 的数组 arr 包含整数 1 到 n随机顺序；例如，它可能是 arr = [4 5 3 6 2 1].

对于arr中的每个元素e，我需要找到最接近的元素k小于 e。（"Closest" 表示位置，而不是值；所以在上面的例子中，5 比 6 更接近 3。）如果在两个方向上都有同样接近的较小元素——如上面例子中的 6，其直接邻居都小于它——那么选择这些元素中的哪一个并不重要。

所以对于上面的例子，arr = [4 5 3 6 2 1]，一个有效的结果是 [3 3 2 2 1 NIL]。

我知道 O(n) 算法可以解决这个问题；它的工作原理是维护一个堆栈，以在每个元素的左侧和右侧找到最近的较小元素。

但令人惊讶的是，一个简单的线性双向搜索比那个算法表现得更好，尽管在我看来它是 O(n²) 在最坏的情况下：

for i = 1 to N
  right = i + 1
  left = i - 1
  while (left > 0 && right <= n)
    // ...find the closest element that is smaller than arr[i] and break while loop

上面的最坏情况下的复杂度是多少？我说得对吗 O(n²)?

Answer 1

这是最坏情况 Θ(n log n) 时间（假设你实施了 Daniel 上面提到的修复——你需要以确保您可以在每个方向上一直扫描到最后）。

首先，观察如果两个元素a和b是邻居，那么a < b 或 b < a。在任何一种情况下，这些元素中至少有一个只需要 "search distance" 1.

推而广之，至少有一半的数组元素需要的搜索距离仅为 1。

同理，如果四个元素[a,b,c,d]都在一排，那么其中一个比另外三个少。所以这些元素中至少有三个需要最多 3 的搜索距离。如上所述，其中两个实际上只需要 1 的搜索距离，所以这实际上意味着两个的搜索距离为 1，第三个有搜索距离最多为 3。总搜索距离最多为 2·1 + 1·3 + (n−1).

我们可以继续这个逻辑增加长度 2^k：我们最多有 2^k−1·(2¹−1) + 2^k−2·(2²−1) + 2^k−3 ·(2³−1) + ⋯ + (n−1).

如果n是2的幂，那么我们可以写成2^k，总搜索距离最多为：
2^k−1·(2¹−1) + 2^k−2·(2²−1) + 2^k−3·(2³−1) + ⋯ + 2⁰·(2^k−1)=
= (2^k−2^k−1) + (2^k−2^k−2) + (2^k−2^k−3) + ⋯ + (2^k−2⁰)
= k·2^k − 2^k + 1
= n log n − log n + 1
< n log n

(如果 n 是 而不是 2 的幂，那么我们可以通过附加值 n+1, n+2, 等等, 直到我们确实有2的幂, 观察得到的总搜索距离小于2n log 2n，仍然在 Θ(n log n).)

当然，上面只是设置了一个上限（O而不是Θ）；但我认为它展示了如何实际实现最坏情况：我们希望以二次幂的方式将最少的数字分散得尽可能远。例如，我们可以 "expand" 这样的列表：

1       2
1   3   2   4
1 5 3 6 2 7 4 8

上述的总搜索距离为 7 + 1 + 2 + 1 + 4 + 1 + 2 + 1 = 17 = 3·8 − 8 + 1，如预测的那样。

以下算法的计算复杂度？

computational complexity of the following algorithm?

arrays

algorithm

complexity-theory