这是问题，在采访中有人问我。
找到数组的最小值和最大值的最佳时间复杂度是多少？
我回答: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)，请更正我。
谢谢
最佳答案
你是对的。除非对数组进行排序，否则您仍然必须检查每一半中的每个元素(重复出现时检查每个四分之一和八分之一)。
唯一的方法是O(log N)，如果您可以在每个递归级别上丢弃一半的搜索空间(例如，在排序列表中搜索特定值)，则唯一可以发生的方法是对它进行排序。
但是，然后，当然，由于您仅获取列表的第一个和最后一个元素，因此根本不需要搜索，因此min和max操作变为O(1)。
现在可能是考官建议将每个问题级别的不同部分分配给不同的执行引擎，以便它们可以并行运行。这是我看到它给您O(log N)的唯一其他方法，但是根据发布的内容，我看不到任何实际证据表明这种情况，而且我认为它将需要相当多的引擎。
关于algorithm - 确实使用分治法改善了在数组中查找最大值和最小值的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27835545/