Лучший алгоритм определения максимума и минимума в массиве чисел?

Question

Я использую здесь псевдокод, но это в JavaScript. С максимально эффективным алгоритмом я пытаюсь найти максимум и минимум, учитывая массив положительных целых чисел. Это то, что я придумал, но я не думаю, что это, вероятно, лучше, и просто задавался вопросом, есть ли у кого-нибудь еще какие-либо предложения.

var low = 1;
var high = 1;
for ( loop numbers ) {
    if ( number > high ) {
        high = number;
    }
    if ( low == 1 ) {
        low = high;
    }
    if ( number < low ) {
        low = number;
    }
}

Answer 1

инициализируйте максимум и минимум, чтобы быть первым элементом. имеет гораздо больше смысла, чем выбор произвольно «высокого» или «низкого» числа.

var myArray = [...],
    low = myArray[0],
    high = myArray[0]
;
// start looping at index 1
for (var i = 1, l = myArray.length; i < l; ++i) {
    if (myArray[i] > high) {
        high = myArray[i];
    } else if (myArray[i] < low) {
        low = myArray[i];
    }
}

или, избегая необходимости многократного просмотра массива:

for (var i = 1, val; (val = myArray[i]) !== undefined; ++i) {
    if (val > high) {
        high = val;
    } else if (val < low) {
        low = val;
    }
}

Answer 2

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

Другими словами, вам нужно пройтись по всем элементам и выполнить проверку максимума и минимума, как у вас.

Сортировка обычно в лучшем случае O(n*log(n)). Таким образом, он медленнее, чем один проход (O(n)).

Answer 3

Ваш пример в значительной степени самый эффективный алгоритм, но, очевидно, он не будет работать, когда все числа меньше 1 или больше 1. Этот код будет работать в следующих случаях:

var low = numbers[0]; // first number in array
var high = numbers[0]; // first number in array
for ( loop numbers ) {
    if ( number > high ) {
        high = number;
    }
    if ( number < low ) {
        low = number;
    }
}

Answer 4

Если список маленький (где «маленький» меньше нескольких тысяч элементов) и вы не делаете это много (где «много» меньше нескольких тысяч раз), это не имеет значения. Сначала профилируйте свой код , чтобы найти реальное узкое место, прежде чем беспокоиться об оптимизации ваших алгоритмов макс / мин.

Теперь, чтобы ответить на вопрос, который вы задали.

Поскольку нет способа избежать просмотра каждого элемента списка, линейный поиск является наиболее эффективным алгоритмом. Требуется N раз, где N - количество элементов в списке. Выполнение всего этого за один цикл более эффективно, чем вызов max (), а затем min () (который занимает 2 * N времени). Таким образом, ваш код в основном правильный, хотя он не учитывает отрицательные числа. Вот оно в Perl.

# Initialize max & min
my $max = $list[0];
my $min = $list[0];
for my $num (@list) {
     $max = $num if $num > $max;
     $min = $num if $num < $min;
}

Сортировка, а затем захват первого и последнего элементов наименее эффективны. Требуется N * log (N), где N - количество элементов в списке.

Наиболее эффективный алгоритм min / max - это алгоритм, в котором min / max пересчитывается каждый раз, когда элемент добавляется или удаляется из списка. По сути, кэширование результата и исключение линейного поиска каждый раз. Время, потраченное на это, - это количество изменений списка. Это занимает самое большее M время, где M - количество изменений, независимо от того, сколько раз вы его называете.

Чтобы сделать это, вы можете рассмотреть дерево поиска, которое сохраняет свои элементы в порядке. Получение минимального / максимального значения в этой структуре составляет O (1) или O (log [n]) в зависимости от того, какой стиль дерева вы используете.

Answer 5

Хотя это все еще алгоритм O (n), вы можете сделать это на 25% быстрее (то есть константа пропорциональности равна 3/2 против 2), сначала сравнив попарно соседние элементы, затем сравнив меньший с минимальным и больший до макс. Я не знаю javascript, но вот он в C ++:

std::pair<int, int> minmax(int* a, int n)
{
  int low = std::numeric_limits<int>::max();
  int high = std::numeric_limits<int>::min();

  for (int i = 0; i < n-1; i += 2) {
    if (a[i] < a[i+i]) {
      if (a[i] < low) {
        low = a[i];
      }
      if (a[i+1] > high) {
        high = a[i+1];
      }
    }
    else {
      if (a[i] > high) {
        high = a[i];
      }
      if (a[i+1] < low) {
        low = a[i+1];
      }
    }
  }

  // Handle last element if we've got an odd array size
  if (a[n-1] < low) {
    low = a[n-1];
  }
  if (a[n-1] > high) {
    high = a[n-1];
  }

  return std::make_pair(low, high);
} 

Answer 6

алгоритм Никфа не лучший способ сделать это. В худшем случае алгоритм Никфа выполняет 2 сравнения на число, в общей сложности 2n - 2.

Мы можем сделать немного лучше. Когда вы сравниваете два элемента a и b, если a> b, мы знаем, что a не является минимумом, а b не является максимумом. Таким образом, мы используем всю доступную информацию, чтобы исключить как можно больше элементов. Для простоты предположим, что у нас есть четное количество элементов.

Разбейте их на пары: (a1, a2), (a3, a4) и т. Д.

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

Сверху, поиск минимума или максимума из n элементов занимает n-1 сравнений. Таким образом, среда выполнения: n / 2 (для начальных сравнений) + n / 2 - 1 (максимум победителей) + n / 2 - 1 (минимум проигравших) = n / 2 + n / 2 + n / 2 -2 = 3n / 2 - 2. Если n нечетно, у нас есть еще один элемент в каждом из наборов, поэтому время выполнения будет 3n / 2

Фактически, мы можем доказать, что это самое быстрое, что эта проблема может быть решена любым алгоритмом.

Пример:

Предположим, наш массив 1, 5, 2, 3, 1, 8, 4 Разделите на пары: (1,5), (2,3) (1,8), (4, -). Сравните. Победители: (5, 3, 8, 4). Проигравшие (1, 2, 1, 4).

Сканирование победителей дает 8. Сканирование проигравших дает 1.

Answer 7

var numbers = [1,2,5,9,16,4,6];

var maxNumber = Math.max.apply(null, numbers);
var minNumber = Math.min.apply(null, numbers);

Answer 8

Javascript-массивы имеют встроенную функцию сортировки, которая принимает функцию для сравнения. Вы можете отсортировать числа и просто взять голову и хвост, чтобы получить минимум и максимум.

var sorted = arrayOfNumbers.sort(function(a, b) { return a - b; }),
    ,min = sorted[0], max = sorted[sorted.length -1];

По умолчанию метод сортировки сортируется лексикографически (в порядке словаря), поэтому вам необходимо передать функцию, которую он будет использовать для числовой сортировки. Передаваемая вами функция должна возвращать 1, -1 или 0, чтобы определить порядок сортировки.

// standard sort function
function sorter(a, b) {
  if (/* some check */)
    return -1; // a should be left of b
  if (/*some other check*/)
    return 1; // a should be to the right of b
  return 0; // a is equal to b (no movement)
}

В случае чисел вы можете просто вычесть второе из первого параметра, чтобы определить порядок.

var numbers = [5,8,123,1,7,77,3.14,-5];

// default lexicographical sort
numbers.sort() // -5,1,123,3.14,5,7,77,8

// numerical sort
numbers.sort(function(a, b) { return a - b; }) // -5,1,123,3.14,5,7,77,8

Answer 9

Испытывая эти фрагменты по-настоящему на V8, алгоритм Дрю Холла работает в 2/3 времени Никфа, как и предсказывалось. Заставив цикл вместо обратного отсчета, сократить его примерно до 59% времени (хотя это больше зависит от реализации). Только слегка проверено:

var A = [ /* 100,000 random integers */];

function minmax() {
    var low = A[A.length-1];
    var high = A[A.length-1];
    var i, x, y;
    for (i = A.length - 3; 0 <= i; i -= 2) {
        y = A[i+1];
        x = A[i];
        if (x < y) {
            if (x < low) {
                low = x;
            }
            if (high < y) {
                high = y;
            }
        } else {
            if (y < low) {
                low = y;
            }
            if (high < x) {
                high = x;
            }
        }
    }
    if (i === -1) {
        x = A[0];
        if (high < x) {
            high = x;
        } else if (x < low) {
            low = x;
        }
    }
    return [low, high];
}

for (var i = 0; i < 1000; ++i) { minmax(); }

Но чувак, это довольно уродливо.

Answer 10

Делая это в ES6, используя расширенный синтаксис :

var arrNums = [1, 2, 3, 4, 5];
Math.max(...arrNums) // 5
Math.min(...arrNums) // 1