使用分治算法是否能改善查找数组中最大值和最小值的时间复杂度？

Question

这是我在面试中被问到的问题。

如何获得查找数组最小值和最大值的最佳时间复杂度？

我的回答是：O(n)。遍历整个数组，同时跟踪迄今为止找到的最大值和最小值。非常简单直接。

面试官问我能否使用分治法来改进它，我说可能不行。然后对话继续进行，最后我被要求实现分治法。

以下是具体实现：

public class MinMaxInArray {
    public static int[] findMinMax(int[] array, int i, int j){
        // base cases
        int arrLen = j - i + 1;
        if (arrLen == 1)
            return new int[]{array[i], array[j]};    //j and i are the same

        if (arrLen == 2){
            int min = Math.min(array[i], array[j]);
            int max = Math.max(array[i], array[j])           
            return new int[]{min, max};
        }

        // actual divide and conquer        
        int mid = i + (j-i)/2;
        int[] leftMinMax = findMinMax(array, i, mid);
        int[] rightMinMax = findMinMax(array, mid+1, j);
        return new int[]{  Math.min(leftMinMax[0], rightMinMax[0]), Math.max(leftMinMax[1], rightMinMax[1])   };
    }

    public static void main(String[] args){
        int[] array = {20, 5, 7, 25, 30, 1, 9, 12};
        int[] minMax= findMinMax(array, 0, array.length - 1);           //minMax[0] = minimum value, minMax[1] = maximum value
        System.out.println("min = " + minMax[0] + ", max = " + minMax[1] );
    }

}

我相信这仍然是O(n)，因为所有元素都被比较了。但是面试官坚持认为它是O(log n)，并让我思考一下。我想了很久，我确信它是O(n)。如果我正确的话，仅仅应用分治法并不能总是降低复杂度。

如果我的理解有误，请纠正我，谢谢。

- brain storm

---

问题本身（迭代/分治）和标题（二分查找）之间有什么联系？ - greybeard

Answer 1

您是正确的。除非数组已排序，否则您仍然需要检查每个半部分中的每个元素（以及每个四分之一和每个八分之一，随着您的递归）。

唯一能够实现 O(log N) 的方法是在每个递归级别上丢弃一半的搜索空间（例如在已排序列表中搜索特定值），而唯一能够发生这种情况的方法是排序。

但是，当然，由于您只需要获取列表的第一个和最后一个元素，因此 min 和 max 操作成为 O(1)，无需进行搜索。

现在也许考官是在提供关于将每个问题级别的不同半部分分配给不同执行引擎以便可以并行运行的分治方法。但是我根据发布的内容没有看到任何真正证据表明这是真的，并且我认为需要相当多的引擎才能实现。

- paxdiablo

---

考官可能也在考虑那些无法放入内存的非常大的数据数组（比如在有限内存设备上），这时分治法可能是一个明智的选择，以避免过多的磁盘交换。 - rossum

Answer 2

使用分治法查找最小值和最大值的时间复杂度确实是O(n)。

但是，使用分治法可以大大减少比较次数，从而在数据量巨大时节省时间。

因此，如果n是2的幂，则分治方法需要进行3/2n-2次比较。如果n不是2的幂，则需要进行超过3/2n-2次比较。

- Abhishek

Answer 3

我也同意“使用分治法查找最小值和最大值”的时间复杂度是O(N)
因为在“分而治之”中
分--->需要O(n)的时间，因为它将每个段分成更小的一部分。
治--->可以是任何给出结果的函数。因此时间复杂度将基于征服正在执行的操作。就像在归并排序中，合并部分需要log(n)的时间。

由于在这种情况下征服是常数操作

- Ibz.Shaikh