algorithm - una - maximo valor absoluto excel

¿Cuál es la mejor manera de obtener el valor mínimo o máximo de una matriz de números?

Question

Digamos que tengo una matriz de números: [2,3,3,4,2,2,5,6,7,2]

¿Cuál es la mejor manera de encontrar el valor mínimo o máximo en esa matriz?

En este momento, para obtener el máximo, estoy recorriendo la Matriz y restableciendo una variable al valor si es mayor que el valor existente:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = 0;
for each (var num:Number in myArray)
{
if (num > maxValue)
maxValue = num;
}

Esto simplemente no parece ser la mejor forma de hacerlo (trato de evitar bucles siempre que sea posible).

Answer 1

A continuación se encuentra la solución con o (n): -

public static void findMaxAndMinValue(int A[]){
int min =0, max = 0;
if(A[0] > A[1] ){
min = A[1];
max = A[0];
}else{
max = A[1];
min = A[0];
}
for(int i = 2;i<A.length ;i++){
if(A[i] > max){
max = A[i];
}
if(min > A[i]){
min = A[i];
}
}
System.out.println("Maxinum Value is "+min+" & Minimum Value is "+max);
}

Answer 2

A menos que la matriz esté ordenada, es lo mejor que obtendrás. Si está ordenado, solo toma el primer y último elemento.

Por supuesto, si no está ordenado, la clasificación primero y el primero y el último se garantiza que serán menos eficientes que el simple bucle de una vez. Incluso los mejores algoritmos de clasificación tienen que mirar cada elemento más de una vez (un promedio de O (log N) veces para cada elemento. Eso es O (N * Log N) total. Un simple escaneo de una vez es solo O (N).

Si desea acceso rápido al elemento más grande en una estructura de datos, eche un vistazo a los montones para una forma eficiente de mantener los objetos en algún tipo de orden.

Answer 3

Depende de lo que llames "lo mejor". Desde un punto de vista teórico, no se puede resolver el problema en menos de O(n) en una máquina determinante de Turing.

El algoritmo ingenuo es demasiado loop y actualiza min, max. Sin embargo, una solución recursiva requerirá menos comparaciones que el algoritmo ingenuo, si desea obtener un mínimo, máximo al mismo tiempo (no es necesariamente más rápido debido a la sobrecarga de llamada a la función).

struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

La solución más simple sería ordenar y obtener el primer y último artículo, aunque obviamente no es el más rápido;)

La mejor solución, basada en el rendimiento, para encontrar el mínimo o máximo es el algoritmo ingenuo que ha escrito (con un solo bucle).

Answer 4

Después de leer los comentarios de todos (gracias por su interés), descubrí que la "mejor" forma (la menor cantidad de código, el mejor rendimiento) para hacer esto era simplemente ordenar la matriz y luego tomar el primer valor en la matriz:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];

Esto también funciona para una matriz de objetos: simplemente usa la función Array.sortOn () y especifica una propiedad:

// Sample data
var myArray:Array /* of XML */ =
[
<item level="2" name="a" />
<item level="3" name="b" />
<item level="3" name="c" />
<item level="2" name="d" />
<item level="5" name="e" />
]
// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);
var lowestLevel:int = myArray[0].@level;

¡Espero que esto ayude a alguien más algún día!

Answer 5

Esto depende de los requisitos de la aplicación del mundo real.

Si su pregunta es meramente hipotética, entonces los conceptos básicos ya han sido explicados. Es un problema típico de búsqueda vs. Ya se ha mencionado que, algorítmicamente, no se logrará mejor que O (n) para ese caso.

Sin embargo, si buscas un uso práctico, las cosas se vuelven más interesantes. Debería considerar qué tan grande es la matriz y los procesos involucrados en agregar y eliminar del conjunto de datos. En estos casos, puede ser mejor tomar el ''acierto'' computacional en el momento de la inserción / eliminación ordenando sobre la marcha. Las inserciones en una matriz preordenada no son tan costosas.

La respuesta de consulta más rápida a la solicitud de Min Max siempre será de una matriz ordenada, ya que, como han mencionado otros, simplemente toma el primer elemento o el último, lo que le da un costo de O (1).

Para obtener un poco más de una explicación técnica sobre los costos computacionales involucrados, y la notación Big O, consulte el artículo de Wikipedia here .

Mella.

Answer 6

Hay varias maneras en que esto se puede hacer.

1. Fuerza bruta. Búsqueda lineal para min y max por separado. (Comparaciones 2N y pasos 2N)
2. Iteramos linealmente y verificamos cada número tanto para min como para max. (Comparaciones 2N)
3. Usa Dividir y conquistar. (Entre comparaciones de 2N y 3N / 2)
4. Comparación por pares que se explica a continuación (Comparaciones 3N / 2)

Cómo encontrar max. y min. en conjunto utilizando comparaciones mínimas?

Si está realmente paranoico con la velocidad, el tiempo de ejecución y el número de comparaciones, consulte también http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

Answer 7

La forma más corta:

Math.min.apply (null, array); // esto devolverá el valor mínimo de la matriz
Math.max.apply (null, array); // esto devolverá el valor máximo de la matriz

de otra manera de obtener el valor mínimo y máximo de la matriz

 function maxVal(givenArray):Number
{
var max = givenArray[0];
for (var ma:int = 0; ma<givenArray.length; ma++)
{
if (givenArray[ma] > max)
{
max = givenArray[ma];
}
}
return max;
}
function minVal(givenArray):Number
{
var min = givenArray[0];
for (var mi:int = 0; mi<givenArray.length; mi++)
{
if (givenArray[mi] < min)
{
min = givenArray[mi];
}
}
return min;
}

Como puede ver, el código en ambas funciones es muy similar. La función establece una variable - max (o min) y luego se ejecuta a través de la matriz con un bucle, verificando cada elemento siguiente. Si el siguiente elemento es más alto que el actual, establézcalo en max (o min). Al final, devuelve el número.

Answer 8

Las respuestas teóricas de todos los demás son buenas, pero seamos pragmáticos. ¡ActionScript proporciona las herramientas que necesita para que ni siquiera tenga que escribir un bucle en este caso!

Primero, tenga en cuenta que Math.min() y Math.max() pueden tomar cualquier cantidad de argumentos. Además, es importante comprender el método apply() disponible para los objetos Function . Le permite pasar argumentos a la función usando una Array . Aprovechemos ambos:

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

Aquí está la mejor parte: el "bucle" se ejecuta en realidad usando código nativo (dentro de Flash Player), por lo que es más rápido que buscar el valor mínimo o máximo usando un bucle de ActionScript puro.

Answer 9

Math.max () es en realidad un código as3 compilado para códigos de operación AVM2, y como tal no es más "nativo" que cualquier otro código as3. Como consecuencia, no es necesariamente la implementación más rápida.

En realidad, dado que funciona en tipo Array, es más lento que el código cuidadosamente escrito.

Hice una comparación de referencia rápida de varias implementaciones ingeniosas de Vector y Array de Math.max, usando PerformanceTest de gskinner (el Vector y la matriz se rellenaron con Números aleatorios idénticos). La implementación de Vector más rápida parecía ser más de 3 veces más rápida que Math.max con el reproductor de SDK / release de AIR reciente (flash player WIN 14,0,0,122 RELEASE, compilado con AIR SDK 14):

Promedio de 3.5 ms para 1,000,000 de valores, en comparación con el promedio de Math.max () de 11ms:

function max(values:Vector.<Number>):Number
{
var max:Number = Number.MIN_VALUE;
var length:uint = values.length;
for (var i:uint = 0; i < length ; ++i)
if (values[i] > max)
max = values[i];
return max;
}

La conclusión es que si le preocupa el rendimiento, debe utilizar Vector over Array en cualquier lugar que pueda, en primer lugar, y no siempre confiar en las implementaciones predeterminadas, especialmente cuando fuerzan el uso de Array.

PD: ¡la misma implementación con un ciclo para cada () ciclo es 12 veces más lenta ...!

Answer 10

No hay ninguna manera confiable de obtener el mínimo / máximo sin probar cada valor. No desea intentar una ordenación ni nada de eso, caminar por la matriz es O (n), que es mejor de lo que cualquier algoritmo de ordenación puede hacer en el caso general.

Answer 11

Si

1. La matriz no está ordenada
2. Encontrar el mínimo y el máximo se realiza simultáneamente

Luego hay un algoritmo que encuentra el mínimo y máximo en 3n / 2 número de comparaciones. Lo que hay que hacer es procesar los elementos de la matriz por parejas. El más grande del par se debe comparar con el máximo actual y el más pequeño del par se debe comparar con el mínimo actual. Además, se necesita tener especial cuidado si la matriz contiene un número impar de elementos.

En código c ++ (tomando prestado algún código de Mehrdad).

struct MinMax{
int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
MinMax min_max;
int index;
int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
if ( n%2 != 0 ){// if n is odd
min_max.Min = array[start];
min_max.Max = array[start];
index = start + 1;
}
else{// n is even
if ( array[start] < array[start+1] ){
min_max.Min = array[start];
min_max.Max = array[start+1];
}
else{
min_max.Min = array[start+1];
min_max.Max = array[start];
}
index = start + 2;
}
int big, small;
for ( int i = index; i < n-1; i = i+2 ){
if ( array[i] < array[i+1] ){ //one comparison
small = array[i];
big = array[i+1];
}
else{
small = array[i+1];
big = array[i];
}
if ( min_max.Min > small ){ //one comparison
min_max.Min = small;
}
if ( min_max.Max < big ){ //one comparison
min_max.Max = big;
}
}
return min_max;
}

Es muy fácil ver que el número de comparaciones que toma es 3n / 2. El ciclo se ejecuta n / 2 veces y en cada iteración se realizan 3 comparaciones. Este es probablemente el óptimo que uno puede lograr. En este momento, no puedo señalar una fuente definida de eso. (Pero, creo que he visto una prueba de eso en alguna parte).

La solución recursiva dada por Mehrdad arriba, probablemente también logre este número mínimo de comparaciones (la última línea necesita ser cambiada). Pero con el mismo número de comparaciones, una solución iterativa siempre superará una solución recursiva debido a una sobrecarga en la llamada de función como mencionó. Sin embargo, si a uno solo le interesa encontrar un mínimo y máximo de algunos números (como lo hace Eric Belair), nadie notará ninguna diferencia en la computadora de hoy con ninguno de los enfoques anteriores. Para una matriz grande, la diferencia puede ser significativa.

Aunque esta solución y la solución dada por Matthew Brubaker tiene O (n) complejidad, en la práctica uno debe evaluar cuidadosamente las constantes ocultas involucradas. El número de comparaciones en su solución es 2n. La aceleración obtenida con la solución con comparaciones 3n / 2 en comparación con 2n comparaciones sería notable.

Answer 12

Si desea encontrar tanto el mínimo como el máximo al mismo tiempo, el ciclo se puede modificar de la siguiente manera:

int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}

Esto debería lograr el tiempo O (n).

Answer 13

Si está construyendo el conjunto una vez y desea encontrar el máximo una sola vez, iterar es lo mejor que puede hacer.

Cuando desee modificar la matriz y ocasionalmente desee saber el elemento máximo, debe usar una Cola de prioridad . Una de las mejores estructuras de datos para eso es un Heap de Fibonacci , si esto es demasiado complicado usa un Binary Heap que es más lento pero aún así es bueno.

Para encontrar el mínimo y máximo, solo construye dos montones y cambia el signo de los números en uno de ellos.

Answer 14

Sorprendido, nadie mencionó el paralelismo aquí.

Si realmente tiene una gran variedad, puede usar parallel-for, en sub rangos. Al final compara todos los sub-rangos. Pero el paralelismo también tiene un poco de penalización, por lo que no se optimizaría en arreglos pequeños. Sin embargo, si tienes grandes conjuntos de datos, comienza a tener sentido, y obtienes una reducción de la división de tiempo cercana a la cantidad de subprocesos que realizan la prueba.

Answer 15

Tenga en cuenta que la ordenación de la matriz será más rápida que el bucle hasta cierto tamaño de la matriz. Si su matriz es pequeña (y será así en cualquier momento), entonces su solución está perfectamente bien. Pero si puede ser demasiado grande, debe usar un condicional para usar el enfoque de ordenación cuando la matriz es pequeña, y la iteración normal cuando es demasiado grande.

Answer 16

Tienes que recorrer la matriz, no hay otra manera de verificar todos los elementos. Solo una corrección para el código: si todos los elementos son negativos, maxValue será 0 al final. Debe inicializarlo con el valor mínimo posible para entero.
Y si va a buscar la matriz muchas veces, es una buena idea ordenarla primero, que la búsqueda es más rápida (búsqueda binaria) y los elementos mínimo y máximo son solo el primero y el último.

Answer 17

Algoritmo MaxMin (primero, último, máximo, mínimo)

// Este algoritmo almacena el elemento más alto y más bajo

// Valores de la matriz global A en las variables globales max y min

// tmax y tmin son variables globales temporales

{
if (first==last) //Sub-array contains single element
{
max=A[first];
min=A[first];
}
else if(first+1==last) //Sub-array contains two elements
{
if(A[first]<A[Last])
{
max=a[last]; //Second element is largest
min=a[first]; //First element is smallest
}
else
{
max=a[first]; //First element is Largest
min=a[last]; //Second element is smallest
}
}
else
//sub-array contains more than two elements
{
//Hence partition the sub-array into smaller sub-array
mid=(first+last)/2;
//Recursively solve the sub-array
MaxMin(first,mid,max,min);
MaxMin(mid+1,last,tmax,tmin);
if(max<tmax)
{
max=tmax;
}
if(min>tmin)
{
min=tmin;
}
}
}