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

Вашим примером является в значительной степени самый эффективный алгоритм, но очевидно он не будет работать, когда все числа будут меньше чем 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;
    }
}

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

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

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

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

Теперь для ответа на вопрос Вы спросили.

Поскольку нет никакого способа постараться не смотреть на каждый элемент списка, линейный поиск является самым эффективным алгоритмом. Требуется время N, где N является числом элементов в списке. Выполнение всего этого в одном цикле более эффективно, чем вызов макс. () затем минута () (который берет 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 * журнал (N), где N является числом элементов в списке.

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

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

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

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

Хотя это - все еще 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);
} 

Единственная дальнейшая оптимизация, которую я предложил бы, оптимизирует сам цикл. Это быстрее для считания в обратном порядке, чем подсчитать в JavaScript.

Принятие списка уже не отсортировано, это о лучшем, которое можно сделать. Можно сохранить себя сравнение путем выполнения следующего (в псевдокоде):

low = +INFINITY
high = -INFINITY
for each n in numbers:
    if n < low:
        low = n
    if n > high:
        high = n

Это - O (n) операция, которая является в основном лучшей, можно сделать.

Испытывая эти отрывки для реального на V8, алгоритм Drew Hall работает в 2/3 времени nickf's, как предсказано. Проведение подсчета цикла вниз вместо сокращает его приблизительно к 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(); }

Но человек, это довольно ужасно.

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

Мы можем сделать немного лучше. Когда Вы сравниваете два элемента a и b, если a> b, мы знаем, что не минута и 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.

В Python:

>>> seq = [1, 2, 3, 4, 5, 6, 7]
>>> max(seq)
7
>>> min(seq)
1

Массивы 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

этот алгоритм работает для O (n) и больше не требуется дополнительной памяти для хранения элементов ...

enter code here
int l=0,h=1,index,i=3;
    if(a[l]>a[h])
                 swap(&a[l],&a[h]);
    for(i=2;i<9;i++)
    {
                                if(a[i]<a[l])
                                {
                                      swap(&a[i],&a[l]);  
                                }
                                if(a[i]>a[h])
                                {
                                             swap(&a[i],&a[h]);
                                }
    }
    printf("Low:  %d  High:  %d",a[0],a[1]);