使用分而治之的方法可以提高时间复杂度,以便在数组中找到最大值和最小值

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),但我看到基于什么张贴提示是这样的话没有真正的证据,我认为这将需要相当多的引擎.