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

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) 的唯一方法是如果您可以在每个递归级别丢弃一半的搜索空间(例如在排序列表中搜索特定值)和唯一方法如果它被排序，就会发生这种情况。

但是，当然，min 和 max 操作变为 O(1)，因为您只获取列表的第一个和最后一个元素，无需搜索完全没有。

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