使用分而治之是否会提高在数组中查找最大值和最小值的时间复杂度

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)。如果我是正确的，仅仅应用分而治之并不总能降低复杂性。

如果我理解这个算法仍然是 O(n)，请纠正我。

谢谢

Answer 1

你是对的。除非对数组进行排序，否则您仍然必须检查每一半中的每个元素（以及重复出现的每四分之一和每八分之一）。

它可以是 O(log N) 的唯一方法是，如果您可以丢弃每个递归级别的一半搜索 space（例如在排序列表中搜索特定值）和只有可能发生的方式是排序。

但是，当然，min 和 max 操作变为 O(1)，因为您只需获取列表的第一个和最后一个元素，根本不需要搜索。

现在可能考官建议分而治之，将每个问题级别的不同部分分配给不同的执行引擎，这样他们就可以运行并行。这是我能看到它给你 O(log N) 的唯一其他方式，但根据发布的内容，我没有看到真正的证据表明情况如此，我认为它需要相当多的引擎。

Answer 2

的确，分而治之求最小值和最大值的时间复杂度是O(n)。

但是使用分而治之的方法可以大大减少比较的次数，如果数据量很大，确实可以减少时间。

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

Answer 3

我也同意“使用分而治之求最小值，最大值”是 O(N)
因为在“分而治之”
划分 ---> 时间复杂度为 O(n)，因为它将每个片段分成更小的片段。
征服--->它可以是给出结果的任何函数。所以时间复杂度将取决于征服正在做什么。与合并排序一样，合并部分需要 log(n) 时间。

因为在这种情况下征服是常量操作

使用分而治之是否会提高在数组中查找最大值和最小值的时间复杂度

does using divide & conquer improve the time complexity to find max and min in an array

algorithm

binary-search

time-complexity

divide-and-conquer