Jaki jest najlepszy sposób, aby uzyskać minimalną lub maksymalną wartość z tablicy liczb?

Nie ma żadnego niezawodnego sposobu na uzyskanie minimum / maksimum bez testowania każdej wartości. Nie chcesz próbować sortowania lub czegoś podobnego, przechodząc przez tablicę to O (n), co jest lepsze niż jakikolwiek algorytm sortowania może zrobić w ogólnym przypadku.

If

1. tablica nie jest sortowana
2. znajdowanie min i max odbywa się jednocześnie

Następnie istnieje algorytm, który znajduje min i max w liczbie porównań 3n/2. Co trzeba zrobić, to przetworzyć elementy tablicy w parach. Większa z pary powinna być porównana z prądem max, a mniejsza z pary powinna być porównana z prądem min. Ponadto należy zachować szczególną ostrożność, jeśli tablica zawiera nieparzystą liczbę żywioły.

W kodzie c++ (zapożyczenie kodu od Mehrdada).

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

Łatwo zauważyć, że liczba porównań wynosi 3n / 2. Pętla działa n / 2 razy i w każdej iteracji wykonuje się 3 porównania. Jest to prawdopodobnie optymalne, które można osiągnąć. W tej chwili nie mogę wskazać konkretnego źródła tego. (Ale chyba gdzieś widziałem na to dowód.)

Rozwiązanie rekurencyjne podane przez mehrdada powyżej, prawdopodobnie również osiąga tę minimalną liczbę porównania (ostatnia linia musi zostać zmieniona). Ale przy tej samej liczbie porównań rozwiązanie iteracyjne zawsze będzie pokonywać rozwiązanie rekurencyjne ze względu na narzut w wywołaniu funkcji, jak wspomniał. Jeśli jednak zależy nam tylko na znalezieniu min i max kilku liczb (jak robi to Eric Belair), nikt nie zauważy żadnej różnicy w dzisiejszym komputerze z którymkolwiek z powyższych podejść. Dla dużej tablicy różnica może być znacząca.

Choć to rozwiązanie i rozwiązanie podane przez Matthew Brubaker ma złożoność O (n), w praktyce należy dokładnie ocenić Ukryte stałe. Liczba porównań w jego rozwiązaniu wynosi 2n. zauważalne byłoby przyspieszenie uzyskane dzięki rozwiązaniu z porównaniami 3n / 2 w przeciwieństwie do porównań 2n.

Jeśli tablica nie jest posortowana, to najlepsze, co dostaniesz. Jeśli jest posortowane, po prostu weź pierwszy i ostatni element.

Oczywiście, jeśli nie jest posortowane, sortowanie najpierw i pobieranie pierwszego i ostatniego jest gwarantowane mniej wydajne niż tylko zapętlenie raz. Nawet najlepsze algorytmy sortowania muszą spojrzeć na każdy element więcej niż jeden raz(średnio O (log N) razy dla każdego elementu. To jest O(n*Log N) razem. Proste skanowanie raz przez to tylko O (N).

Jeśli jeśli chcesz uzyskać szybki dostęp do największego elementu struktury danych, spójrz na sterty, aby znaleźć skuteczny sposób na utrzymanie obiektów w jakiejś kolejności.

Musisz przełączyć tablicę w pętlę, nie ma innego sposobu na sprawdzenie wszystkich elementów. Wystarczy jedna korekta kodu - jeśli wszystkie elementy są ujemne, maxValue będzie na końcu równe 0. Powinieneś zainicjować go z minimalną możliwą wartością dla liczby całkowitej.
A jeśli zamierzasz przeszukiwać tablicę wiele razy, dobrze jest najpierw ją posortować, niż wyszukiwanie jest szybsze (wyszukiwanie binarne), a elementy minimalne i maksymalne są tylko pierwszymi i ostatnimi.

Zależy od tego, co nazywasz "najlepszym."Z teoretycznego punktu widzenia nie można rozwiązać problemu w mniej niż O(n) w deterministycznej maszynie Turinga.

Naiwny algorytm jest zbyt loop i update min, max. Jednak rozwiązanie rekurencyjne będzie wymagało mniej porównań niż naiwny algorytm, jeśli chcesz uzyskać min, max jednocześnie (niekoniecznie jest to szybsze ze względu na narzut wywołania funkcji).

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

Najprostszym rozwiązaniem byłoby posortowanie i uzyskanie pierwszego i ostatniego elementu, choć oczywiście nie jest najszybszy;)

Najlepszym rozwiązaniem pod względem wydajności, aby znaleźć minimum lub maksimum jest naiwny algorytm, który napisałeś (z pojedynczą pętlą).

Matematyka.max() jest w rzeczywistości kodem AS3 skompilowanym do kodu opcodes AVM2 i jako taki nie jest bardziej "natywny" niż jakikolwiek inny kod as3. W konsekwencji niekoniecznie jest to najszybsze wdrożenie.

Właściwie, biorąc pod uwagę, że działa on na typie tablicy, jest wolniejszy niż starannie napisany wektor kodu:

Zrobiłem szybkie porównanie porównawcze kilku naiwnych wektorowych i macierzowych implementacji matematyki.max, używając Gskinner ' s PerformanceTest (Wektor i tablica są wypełnione identycznymi losowymi Liczby). Najszybsza implementacja wektorowa okazała się ponad 3x szybsza od matematyki.max z najnowszym AIR SDK / release player (wersja flash player WIN 14,0,0,122, skompilowana z AIR SDK 14):

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

Wniosek jest taki, że jeśli chodzi o wydajność, powinieneś używać Vector over Array wszędzie, gdzie tylko możesz, i nie zawsze polegać na domyślnych implementacjach, zwłaszcza gdy Wymuś użycie tablicy

PS: ta sama implementacja z pętlą for each() jest 12x wolniejsza ...!

Zależy to od rzeczywistych wymagań aplikacji.

Jeśli twoje pytanie jest tylko hipotetyczne, to podstawy zostały już wyjaśnione. Jest to typowy problem wyszukiwania a sortowania. Już wspomniano, że algorytmicznie nie osiągniesz lepszego niż O (n) w tym przypadku.

Jednak, jeśli patrzysz na praktyczne zastosowanie, rzeczy stają się bardziej interesujące. Trzeba by wtedy rozważyć, jak duża jest tablica, oraz procesy zaangażowane w dodawanie i usunięcie ze zbioru danych. W takich przypadkach najlepiej jest wykonać obliczeniowe "trafienie" w czasie wstawiania / usuwania poprzez sortowanie w locie. Wstawki do wstępnie posortowanej tablicy nie są tak drogie.

Najszybsza odpowiedź zapytania na żądanie Min Max będzie zawsze z posortowanej tablicy, ponieważ jak inni wspominali, po prostu bierzesz pierwszy lub ostatni element - dając Ci koszt O(1).

Dla nieco bardziej technicznego wyjaśnienia kosztów obliczeniowych i Big O notation, sprawdź artykuł w Wikipedii tutaj .

Nick.

Jeśli budujesz tablicę raz i chcesz znaleźć maksimum tylko raz, iteracja jest najlepszym, co możesz zrobić.

Jeśli chcesz zmodyfikować tablicę i czasami chcesz znać maksymalny element, powinieneś użyć kolejki priorytetów . Jedną z najlepszych struktur danych do tego jest sterta Fibonacciego , jeśli jest to zbyt skomplikowane, użyj sterty binarnej , która jest wolniejsza, ale nadal dobra.

Aby znaleźć minimum i maksimum, wystarczy zbudować dwie stosy i zmienić znak cyfr w jednym z nich.

Proszę wziąć pod uwagę, że sortowanie tablicy będzie tylko szybsze niż zapętlanie do pewnej wielkości tablicy. Jeśli Twoja tablica jest mała (i będzie tak zawsze), Twoje rozwiązanie jest w porządku. Ale jeśli może być zbyt duża, powinieneś użyć warunkowego, aby użyć metody sortowania, gdy tablica jest mała, i normalnej iteracji, gdy jest zbyt duża

Jeśli chcesz znaleźć zarówno min jak i max w tym samym czasie, pętlę można zmodyfikować w następujący sposób:

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

To powinno osiągnąć O (n) timing.

Najkrótsza droga:

Matematyka./ min.apply (null,array); / / zwróci wartość min z array
Matematyka.max.apply (null,array); / / zwróci wartość max z array

Inny sposób uzyskiwania wartości min i max z tablicy

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

Jak widzisz, kod w obu tych funkcjach jest bardzo podobny. Funkcja ustawia zmienną-max (lub min), a następnie biegnie przez tablicę za pomocą pętli, sprawdzając każdy następny element. Jeśli następny element jest wyższy od bieżącego, ustaw go do max (lub min). W końcu zwróć numer.

Można to zrobić na wiele sposobów.

Brutalna siła. Wyszukiwanie liniowe zarówno min jak i max osobno. (2N porównania i 2N kroki)
1. powtarzaj liniowo i sprawdzaj każdą liczbę zarówno dla min, jak i max. (2N)
2. Użyj podziel i podbij. (między 2N a 3N/2N)
3. Porównaj według par wyjaśnionych poniżej (porównania 3N/2)

Jak znaleźć Maxa. i min. w tablicy przy użyciu minimum porównania?

Jeśli naprawdę masz paranoję na temat szybkości, czasu pracy i liczby porównań, zapoznaj się również z http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

Algorytm MaxMin (pierwszy, ostatni, max, min)

//algorytm ten przechowuje najwyższy i najniższy element

//wartości globalnej tablicy A w zmiennych globalnych max i min

//Tmax i tmin są tymczasowymi zmiennymi globalnymi

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

Poniżej rozwiązanie Z 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);
}

Dziwi mnie, że nikt tu nie wspomniał o paralelizmie.

Jeśli masz naprawdę ogromną tablicę, możesz użyć parallel-for, na podzakresach. W końcu Porównaj wszystkie podzakresy. Ale paralelizm też przychodzi, więc nie byłoby to optymalne na małych tablicach. Jednak jeśli masz ogromne zbiory danych, zaczyna to mieć sens, a otrzymasz redukcję podziału czasu zbliżającą się do ilości wątków wykonujących test.

Po przeczytaniu wszystkich komentarzy (dziękuję za zainteresowanie), odkryłem, że "najlepszym" sposobem (najmniejsza ilość kodu, najlepsza wydajność), aby to zrobić, było po prostu posortowanie tablicy, a następnie pobranie pierwszej wartości w tablicy:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

Działa to również dla tablicy obiektów - po prostu używasz tablicy.funkcja sortOn () i podaj Właściwość:

// 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;

Mam nadzieję, że to kiedyś pomoże komuś innemu!