делает использование divide & conquer улучшает сложность времени, чтобы найти max и min в массиве

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 (п), так как все элементы сравниваются. Но интервьюер настаивал на том, что это O (log n), и попросил меня подумать об этом. Я думал совсем немного, и я убежден, что это O (n). Просто применение divide и conquer не всегда уменьшает сложность, если я прав.

Пожалуйста, исправьте меня, если я понимаю, что этот алгоритм все еще O (n).

Спасибо

Answer 1

Вы правы. Если массив не отсортирован, вам все равно придется проверять каждый элемент в каждой половине (и каждую четверть и каждую восьмую, когда вы повторяетесь).

Единственный способ это может быть O (журнал N), если вы можете отбросить за половину пространства поиска каждого уровня рекурсии (например поиск определенного значения в отсортированном списке) и только так, что может случиться, если он отсортирован.

Но тогда, конечно, операции min и max становятся О (1), так как вы просто захватываете первый и последний элемент списка, не нужно искать вообще.

Теперь может быть в том, что экзаменатор предлагал разделить-и-завоевать с точки зрения сельского хозяйства с разных половин каждого уровня проблемы различным машинам исполнения, чтобы они могли работать параллельно. Это единственный другой способ, которым я мог видеть, что он дает вам O (log N), но я не вижу никаких реальных доказательств, основанных на том, что опубликовано, что предполагает, что это так, и я думаю, что для этого потребуется немало движков.

Answer 2

Это правда, что использование разделить и преодолеть сложность времени для нахождения min и max равно O (n).

Но использование разделить и преодолеть количество сравнений можно уменьшить в значительной степени, что действительно сокращает время, если данные огромны.

Так разделяй и властвуй подход делает 3/2n -2 сравнения, если п является степенью 2. И это не более чем на 3/2n -2 сравнения, если п не является степенью 2.