首页 文章

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

提问于
浏览 次
5

这是个问题，我在接受采访时被问到了 .

找到最小和最大数组的最佳时间复杂度是多少？

我回答：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），请纠正我 .

谢谢

algorithm time-complexity binary-search divide-and-conquer

2 回答

  • 7

    你是对的 . 除非数组已排序，否则您仍需检查每一半中的每个元素（每个季度和每个八分之一重复） .

    它可以是O（log N）的唯一方法是，如果您可以丢弃每个递归级别的搜索空间的一半（例如在排序列表中搜索特定值），并且唯一可能发生的方式是它是否已排序 .

    但是，当然， min 和 max 操作变为O（1），因为你只需 grab 列表的第一个和最后一个元素，根本不需要搜索 .

    现在可能是审查员建议在将每个问题级别的不同部分耕种到不同的执行引擎方面进行分而治之，这样它们就可以并行运行 . 发布的那个's the only other way I could see it giving you O(log N) but I see no real evidence based on what's表明情况就是如此，我认为它需要相当多的引擎 .

    回复于
  • 0

    确实，使用除法和征服时间复杂度来找到最小值和最大值是O（n） .

    但是，使用分而治之的比较数量可以在很大程度上减少，如果数据量很大，确实会减少时间 .

    因此，如果n是2的幂，则除法和征服方法进行3 / 2n -2比较 . 如果n不是2的幂，则它进行超过3 / 2n -2比较 .

    回复于

相关问题