Comment trouver le max. et min. dans le tableau à l'aide de minimum de comparaisons?

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

De cette façon que vous feriez 3 comparaisons de 2 éléments, s'élevant à 3N/2 total des comparaisons pour N éléments.

aller pour diviser et conquérir !

1,3,2,5

pour cette découverte min,max va prendre 6 comparaisons

mais les diviser

1,3 ---> will give min 1 and max 3 in one comparison
2,5 ---> will give min 2 and max 5 in one comparison 

maintenant, nous pouvons comparer les deux minutes et maxs

min(1,2) --> will give the final min as 1 (one comparison)
max(3,5) ---> will give the final max as 5 (one comparison)

donc un total de quatre comparaisons pour trouver à la fois des min et max.

Force Brute est plus RAPIDE!

J'aimerais quelqu'un pour me montrer l'erreur de mes moyens, ici, mais, ...

J'ai comparé les temps d'exécution de la force brute méthode contre le (beau) récursive diviser et conquérir. Résultats typiques (en 10 000 000 d'appels pour chaque fonction):

Brute force :
  0.657 seconds 10 values => 16 comparisons.  Min @ 8, Max @ 10
  0.604 seconds 1000000 values => 1999985 comparisons.  Min @ 983277, Max @ 794659
Recursive :
  1.879 seconds 10 values => 13 comparisons.  Min @ 8, Max @ 10
  2.041 seconds 1000000 values => 1499998 comparisons.  Min @ 983277, Max @ 794659

Étonnamment, la force brute de la méthode était d'environ 2,9 fois plus rapide pour un tableau de 10 éléments, et 3,4 fois plus rapide pour un tableau de 1 000 000 d'articles.

De toute évidence, le nombre de comparaisons est pas le problème, mais peut-être le nombre de ré-affectations, et la surcharge de l'appel d'une fonction récursive (ce qui pourrait expliquer pourquoi 1 000 000 de valeurs plus lent que les 10 valeurs).

Mises en garde : je l'ai fait en VBA, C, et j'ai été en comparant les nombres de double précision et le retour de l'index dans le tableau des valeurs Min et Max.

Voici le code que j'ai utilisé (classe cPerformanceCounter n'est pas inclus ici, mais utilise QueryPerformanceCounter haute résolution pour le timing) :

Option Explicit

'2014.07.02

Private m_l_NumberOfComparisons As Long

Sub Time_MinMax()

   Const LBOUND_VALUES As Long = 1

   Dim l_pcOverall As cPerformanceCounter
   Dim l_d_Values() As Double
   Dim i As Long, _
       k As Long, _
       l_l_UBoundValues As Long, _
       l_l_NumberOfIterations As Long, _
       l_l_IndexOfMin As Long, _
       l_l_IndexOfMax As Long

   Set l_pcOverall = New cPerformanceCounter

   For k = 1 To 2

      l_l_UBoundValues = IIf(k = 1, 10, 1000000)

      ReDim l_d_Values(LBOUND_VALUES To l_l_UBoundValues)

      'Assign random values
      Randomize '1 '1 => the same random values to be used each time
      For i = LBOUND_VALUES To l_l_UBoundValues
         l_d_Values(i) = Rnd
      Next i
      For i = LBOUND_VALUES To l_l_UBoundValues
         l_d_Values(i) = Rnd
      Next i

      'This keeps the total run time in the one-second neighborhood
      l_l_NumberOfIterations = 10000000 /l_l_UBoundValues

      '——————— Time Brute Force Method —————————————————————————————————————————
      l_pcOverall.RestartTimer

      For i = 1 To l_l_NumberOfIterations

         m_l_NumberOfComparisons = 0

         IndexOfMinAndMaxDoubleBruteForce _
               l_d_Values, _
               LBOUND_VALUES, _
               l_l_UBoundValues, _
               l_l_IndexOfMin, _
               l_l_IndexOfMax

      Next

      l_pcOverall.ElapsedSecondsDebugPrint _
            3.3, , _
            " seconds Brute-Force " & l_l_UBoundValues & " values => " _
            & m_l_NumberOfComparisons & " comparisons. " _
            & " Min @ " & l_l_IndexOfMin _
            & ", Max @ " & l_l_IndexOfMax, _
            True
      '——————— End Time Brute Force Method —————————————————————————————————————

      '——————— Time Brute Force Using Individual Calls —————————————————————————
      l_pcOverall.RestartTimer

      For i = 1 To l_l_NumberOfIterations

         m_l_NumberOfComparisons = 0

         l_l_IndexOfMin = IndexOfMinDouble(l_d_Values)
         l_l_IndexOfMax = IndexOfMaxDouble(l_d_Values)

      Next

      l_pcOverall.ElapsedSecondsDebugPrint _
            3.3, , _
            " seconds Individual  " & l_l_UBoundValues & " values => " _
            & m_l_NumberOfComparisons & " comparisons. " _
            & " Min @ " & l_l_IndexOfMin _
            & ", Max @ " & l_l_IndexOfMax, _
            True
      '——————— End Time Brute Force Using Individual Calls —————————————————————

      '——————— Time Recursive Divide and Conquer Method ————————————————————————
      l_pcOverall.RestartTimer

      For i = 1 To l_l_NumberOfIterations

         m_l_NumberOfComparisons = 0

         IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
               l_d_Values, _
               LBOUND_VALUES, _
               l_l_UBoundValues, _
               l_l_IndexOfMin, l_l_IndexOfMax

      Next

      l_pcOverall.ElapsedSecondsDebugPrint _
            3.3, , _
            " seconds Recursive   " & l_l_UBoundValues & " values => " _
            & m_l_NumberOfComparisons & " comparisons. " _
            & " Min @ " & l_l_IndexOfMin _
            & ", Max @ " & l_l_IndexOfMax, _
            True
      '——————— End Time Recursive Divide and Conquer Method ————————————————————

   Next k

End Sub

'Recursive divide and conquer
Sub IndexOfMinAndMaxDoubleRecursiveDivideAndConquer( _
      i_dArray() As Double, _
      i_l_LBound As Long, _
      i_l_UBound As Long, _
      o_l_IndexOfMin As Long, _
      o_l_IndexOfMax As Long)

   Dim l_l_IndexOfLeftMin As Long, _
       l_l_IndexOfLeftMax As Long, _
       l_l_IndexOfRightMin As Long, _
       l_l_IndexOfRightMax As Long, _
       l_l_IndexOfMidPoint As Long

   If (i_l_LBound = i_l_UBound) Then 'Only one element

      o_l_IndexOfMin = i_l_LBound
      o_l_IndexOfMax = i_l_LBound

   ElseIf (i_l_UBound = (i_l_LBound + 1)) Then 'Only two elements

      If (i_dArray(i_l_LBound) > i_dArray(i_l_UBound)) Then
         o_l_IndexOfMin = i_l_UBound
         o_l_IndexOfMax = i_l_LBound
      Else
         o_l_IndexOfMin = i_l_LBound
         o_l_IndexOfMax = i_l_UBound
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   Else 'More than two elements => recurse

      l_l_IndexOfMidPoint = (i_l_LBound + i_l_UBound) /2

      'Find the min of the elements in the left half
      IndexOfMinAndMaxDoubleRecursiveDivideAndConquer _
            i_dArray, _
            i_l_LBound, _
            l_l_IndexOfMidPoint, _
            l_l_IndexOfLeftMin, _
            l_l_IndexOfLeftMax

      'Find the min of the elements in the right half
      IndexOfMinAndMaxDoubleRecursiveDivideAndConquer i_dArray, _
            l_l_IndexOfMidPoint + 1, _
            i_l_UBound, _
            l_l_IndexOfRightMin, _
            l_l_IndexOfRightMax

      'Return the index of the lower of the two values returned
      If (i_dArray(l_l_IndexOfLeftMin) > i_dArray(l_l_IndexOfRightMin)) Then
         o_l_IndexOfMin = l_l_IndexOfRightMin
      Else
         o_l_IndexOfMin = l_l_IndexOfLeftMin
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

      'Return the index of the lower of the two values returned
      If (i_dArray(l_l_IndexOfLeftMax) > i_dArray(l_l_IndexOfRightMax)) Then
         o_l_IndexOfMax = l_l_IndexOfLeftMax
      Else
         o_l_IndexOfMax = l_l_IndexOfRightMax
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   End If

End Sub

Sub IndexOfMinAndMaxDoubleBruteForce( _
      i_dArray() As Double, _
      i_l_LBound As Long, _
      i_l_UBound As Long, _
      o_l_IndexOfMin As Long, _
      o_l_IndexOfMax As Long)

   Dim i As Long

   o_l_IndexOfMin = i_l_LBound
   o_l_IndexOfMax = o_l_IndexOfMin

   For i = i_l_LBound + 1 To i_l_UBound

      'Usually we will do two comparisons
      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 2

      If (i_dArray(i) < i_dArray(o_l_IndexOfMin)) Then

         o_l_IndexOfMin = i

         'We don't need to do the ElseIf comparison
         m_l_NumberOfComparisons = m_l_NumberOfComparisons - 1

      ElseIf (i_dArray(i) > i_dArray(o_l_IndexOfMax)) Then

         o_l_IndexOfMax = i

      End If
   Next i

End Sub

Function IndexOfMinDouble( _
      i_dArray() As Double _
      ) As Long

   Dim i As Long

   On Error GoTo EWE

   IndexOfMinDouble = LBound(i_dArray)

   For i = IndexOfMinDouble + 1 To UBound(i_dArray)

      If (i_dArray(i) < i_dArray(IndexOfMinDouble)) Then
         IndexOfMinDouble = i
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   Next i

   On Error GoTo 0
   Exit Function
EWE:
   On Error GoTo 0
   IndexOfMinDouble = MIN_LONG
End Function

Function IndexOfMaxDouble( _
      i_dArray() As Double _
      ) As Long

   Dim i As Long

   On Error GoTo EWE

   IndexOfMaxDouble = LBound(i_dArray)

   For i = IndexOfMaxDouble + 1 To UBound(i_dArray)

      If (i_dArray(i) > i_dArray(IndexOfMaxDouble)) Then
         IndexOfMaxDouble = i
      End If

      m_l_NumberOfComparisons = m_l_NumberOfComparisons + 1

   Next i

   On Error GoTo 0
   Exit Function
EWE:
   On Error GoTo 0
   IndexOfMaxDouble = MIN_LONG
End Function

Un simple pseudo code de l'algorithme récursif:

Function MAXMIN (A, low, high)
    if (high − low + 1 = 2) then 
      if (A[low] < A[high]) then
         max = A[high]; min = A[low].
         return((max, min)).
      else
         max = A[low]; min = A[high].
         return((max, min)).
      end if
   else
      mid = low+high/2
      (max_l , min_l ) = MAXMIN(A, low, mid).
      (max_r , min_r ) =MAXMIN(A, mid + 1, high).
   end if

   Set max to the larger of max_l and max_r ; 
   likewise, set min to the smaller of min_l and min_r .

   return((max, min)).

Mon divide & conquer approche avec java jusqu'à présent:

        public class code {    
    static int[] A = {444,9,8,6,199,3,0,5,3,200};
    static int min = A[0], max = A[1];
    static int count = 0;

    public void minMax(int[] A, int i, int j) {     
        if(i==j) {
            count = count + 2;
            min = Math.min(min, A[i]);
            max = Math.max(max, A[i]);
        }

        else if(j == i+1) {
            if(A[i] > A[j]) {
                count = count + 3;
                min = Math.min(min, A[j]);
                max = Math.max(max, A[i]);
            }
            else {
                count = count + 3;
                min = Math.min(min, A[i]);
                max = Math.max(max, A[j]);
            }
        }

        else {
            minMax(A,i,(i+j)/2);
            minMax(A,(i+j)/2+1,j);
        }
    }

    public static void main(String[] args) {
        code c = new code();
        if(Math.min(A[0], A[1]) == A[0]) {
            count++;
            min = A[0];
            max = A[1];
        }
        else {
            count++;
            min = A[1];
            max = A[0];
        }
        c.minMax(A,2,A.length-1);
        System.out.println("Min: "+min+" Max: "+max);
        System.out.println("Total comparisons: " + count);
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    set<int> t;
    for(int i=0;i<n;i++)
    {

        int x;
        cin>>x;
        t.insert(x);
    }
    set<int>::iterator s,b;
    s=t.begin();
    b=--t.end();
    cout<< *s<<" "<<*b<<endl;


    enter code here

    return 0;
}

//cela peut être fait en log(n) la complexité!!!