¿El mejor algoritmo para determinar el máximo y mínimo en una matriz de números?

Question

Estoy usando pseudocódigo aquí, pero esto está en JavaScript. Con el algoritmo más eficiente posible, estoy tratando de encontrar el alto y el bajo dado un conjunto de números enteros positivos. Esto es lo que se me ocurrió, pero no creo que sea probablemente lo mejor, y me preguntaba si alguien tiene alguna otra sugerencia.

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

inicialice el elemento alto y bajo para ser el primero. tiene mucho más sentido que elegir un número arbitrariamente "alto" o "bajo".

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]; 
    } 
} 

o, evitando la necesidad de buscar el array varias veces:

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

Answer 2

en Python:

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

Answer 3

Tienes que hacerlo en O(n) tiempo porque hay que recorrer todos (n) de los elementos para comprobar ellos porque cualquiera de los elementos puede ser el mínimo o máximo (A menos que ya estén clasificados.)

En otras palabras, necesita recorrer todos los elementos y hacer la comprobación máxima y mínima como usted.

La clasificación es generalmente O(n*log(n)). Por lo tanto, es más lento que un solo barrido (O(n)).

Answer 4

Suponiendo que la lista no está ya ordenada, es lo mejor que puede hacer. Puede ahorrarse una comparación de la siguiente manera (en pseudocódigo):

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

Esta es una operación O (n), que es básicamente lo mejor que puede hacer.

Answer 5

Su ejemplo es más o menos el algoritmo más eficiente, pero, obviamente, no va a funcionar cuando todos los números son menos que 1 o mayor que 1. Este código funciona en esos casos:

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 6

Si la lista es pequeña (donde "pequeña" es inferior a unos pocos miles eL ements) y no lo haces mucho (donde "mucho" es menos de unos miles de veces) no importa. Primero describa su código para encontrar el cuello de botella real antes de preocuparse por la optimización de sus algoritmos de máximo/mínimo.

Ahora para responder la pregunta que ha hecho.

Como no hay forma de evitar mirar cada elemento de la lista, una búsqueda lineal es el algoritmo más eficiente. Lleva N tiempo, donde N es la cantidad de elementos en la lista. Hacerlo todo en un ciclo es más eficiente que llamar a max() y luego a min() (que toma 2 * N tiempo). Entonces, su código es básicamente correcto, aunque no da cuenta de los números negativos. Aquí está en 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; 
} 

Ordenando y luego agarrando el primer y último elemento es el menos eficiente. Se necesita N * log (N) donde N es la cantidad de elementos en la lista.

El algoritmo mínimo/máximo más eficiente es aquel en el que se recalcula min/max cada vez que se agrega o quita un elemento de la lista.En efecto, almacenar en caché el resultado y evitar una búsqueda lineal cada vez. El tiempo dedicado a esto es el número de veces que se cambia la lista. Toma, a lo sumo, M hora, donde M es el número de cambios sin importar cuántas veces lo llame.

Para hacer eso, podría considerar un árbol de búsqueda que mantenga sus elementos en orden. Obtener el min/max en esa estructura es O (1) u O (log [n]) dependiendo del estilo de árbol que use.

Answer 7

La única optimización adicional que sugeriría es optimizar el bucle en sí. Es más rápido contar hacia atrás que contar en JavaScript.

Answer 8

Aunque todavía es un algoritmo O (n), puede hacerlo un 25% más rápido (es decir, la constante de proporcionalidad es 3/2 contra 2) comparando elementos adyacentes primero por pares, luego comparando los más pequeños con los mínimos y mayor a max. No sé javascript, pero aquí está en C++: Algoritmo

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 9

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

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

Answer 10

de nickf no es la mejor manera de hacer esto. En el peor de los casos, el algoritmo de nickf hace 2 comparaciones por número, para un total de 2n - 2.

Podemos hacerlo un poco mejor. Cuando comparas dos elementos a y b, si a> b sabemos que a no es el mínimo, yb no es el máximo. De esta manera usamos toda la información disponible para eliminar tantos elementos como podamos. Por simplicidad, supongamos que tenemos un número par de elementos.

romperlos en pares: (a1, a2), (a3, a4), etc.

Compárelos, rompiéndolas en un conjunto de ganadores y perdedores - esto se lleva a n/2 compara, que nos da dos juegos de tamaño n/2. Ahora encuentra el máximo de los ganadores y el mínimo de los perdedores.

Desde arriba, encontrar el mínimo o el máximo de n elementos toma n-1 compara. Por lo tanto, el tiempo de ejecución es: n/2 (para las comparaciones iniciales) + n/2 - 1 (máximo de ganadores) + n/2 - 1 (mínimo de perdedores) = n/2 + n/2 + n/2 -2 = 3n/2 - 2. Si n es impar, tenemos un elemento más en cada uno de los conjuntos, por lo que el tiempo de ejecución será 3n/2

De hecho, podemos demostrar que este es el más rápido este problema puede ser posiblemente resuelto por cualquier algoritmo.

Un ejemplo:

Supongamos que nuestro matriz es 1, 5, 2, 3, 1, 8, 4 Divide en pares: (1,5), (2,3) (1,8), (4, -). Comparar. Los ganadores son: (5, 3, 8, 4). Los perdedores son (1, 2, 1, 4).

Escaneo de los ganadores da 8. Comprobar que los perdedores da 1.

Answer 11

Tratando estos fragmentos a cabo de verdad en V8, el algoritmo de Drew Salón ejecuta en 2/3 del tiempo de la nickf, como se predijo. Al hacer que el bucle baje la cuenta en lugar de subir, se reduce a aproximadamente el 59% del tiempo (aunque eso depende más de la implementación). Sólo se ha probado ligeramente:

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(); } 

Pero hombre, es bastante feo.

Answer 12

Las matrices de Javascript tienen una función de clasificación nativa que acepta una función para usar en la comparación. Puede ordenar los números y simplemente tomar la cabeza y la cola para obtener el mínimo y el máximo.

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

Por defecto, el método sort ordena lexicográfico (orden de diccionario) así que por eso usted tiene que pasar en una función para la que va a utilizar para conseguir la clasificación numérica. La función que pasa debe devolver 1, -1 o 0 para determinar el orden de clasificación.

// 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) 
} 

En el caso de los números, simplemente puede restar el segundo del primer parámetro para determinar el orden.

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 13

este algoritmo funciona de O (n) y la memoria no más extra necesario para almacenar los elementos ...

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]); 

Answer 14

Hacerlo de la manera ES6 usando spread syntax:

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