Comment trouver le max. et min. en tableau utilisant des comparaisons minimales?
C'est une question d'interview: étant donné un tableau d'entiers trouver le max. et min. en utilisant des comparaisons minimales.
évidemment, je peux boucler le tableau deux fois et utiliser ~2n comparaisons dans le pire des cas, mais je voudrais faire mieux.
12 réponses
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, vous feriez 3 comparaisons pour 2 éléments, s'élevant à 3N/2 comparaisons totales pour N éléments.
s'efforcent d'améliorer la réponse par srbh.kmr. Disons que nous avons la séquence:
A = [a1, a2, a3, a4, a5]
comparer a1 & a2 et calculer min12 , max12 :
if (a1 > a2)
min12 = a2
max12 = a1
else
min12 = a1
max12 = a2
calculer de la même façon min34 , max34 . Puisque a5 est seul, gardez-le tel quel...
Comparez maintenant min12 et min34 et calculez min14 , calculez de la même façon max14 . Enfin, comparez min14 et a5 pour calculer min15 . De même, calculer max15 .
en tout, ce n'est que 6 comparaisons!
Cette solution peut être étendue à un tableau de longueur arbitraire. Peut probablement être mis en œuvre par une approche similaire de fusion-tri (briser le tableau en deux et calculer min max pour chaque moitié).
mise à JOUR: , Voici la code récursif en C:
#include <stdio.h>
void minmax (int* a, int i, int j, int* min, int* max) {
int lmin, lmax, rmin, rmax, mid;
if (i == j) {
*min = a[i];
*max = a[j];
} else if (j == i + 1) {
if (a[i] > a[j]) {
*min = a[j];
*max = a[i];
} else {
*min = a[i];
*max = a[j];
}
} else {
mid = (i + j) / 2;
minmax(a, i, mid, &lmin, &lmax);
minmax(a, mid + 1, j, &rmin, &rmax);
*min = (lmin > rmin) ? rmin : lmin;
*max = (lmax > rmax) ? lmax : rmax;
}
}
void main () {
int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11};
int min, max;
minmax (a, 0, 9, &min, &max);
printf ("Min : %d, Max: %d\n", min, max);
}
Maintenant, je ne peut pas indiquer le nombre exact de comparaisons en termes de N (le nombre d'éléments dans le tableau). Mais il est difficile de voir comment on peut passer en dessous de ces nombreuses comparaisons.
mise à JOUR: Nous pouvons travailler sur le nombre de comparaisons comme ci-dessous:
au bas de cet arbre de calculs, nous formons des paires d'entiers à partir du tableau original. Nous avons donc ont N / 2 nodules de feuilles. Pour chacun de ces noeuds foliaires nous faisons exactement 1 comparaison.
en se référant aux propriétés d'un arbre binaire parfait , nous avons:
leaf nodes (L) = N / 2 // known
total nodes (n) = 2L - 1 = N - 1
internal nodes = n - L = N / 2 - 1
pour chaque noeud interne nous faisons 2 comparaisons. Par conséquent, nous avons N - 2 comparaisons. Avec le N / 2 comparaisons aux noeuds de feuilles, nous avons (3N / 2) - 2 comparaisons totales.
donc, peut-être que c'est la solution srbh.kmr implicite dans sa réponse.
aller pour diviser et conquérir !
1,3,2,5
pour cette constatation min, max prendra 6 comparaisons
mais les diviser
1,3 - - - > donne min 1 et max 3 dans une comparaison 2,5 - - - > donne min 2 et max 5 en une comparaison
maintenant nous pouvons comparer deux minutes (1,2) --> donnera la min finale comme 1 (une comparaison) de même, deux max (3,5) ---> donneront le max final comme 5( une comparaison)
, donc un total de quatre comparaisons
une approche Un peu différente, qui utilise l'arithmétique des nombres entiers au lieu de comparaisons (ce qui n'est pas explicitement interdit)
for(int i=0;i<N;i++) {
xmin += x[i]-xmin & x[i]-xmin>>31;
xmax += x[i]-xmax & xmax-x[i]>>31;
}
la force Brute est plus rapide!
j'aimerais que quelqu'un me montre l'erreur de mes voies, 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 appels à 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 méthode de la force brute était environ 2,9 fois plus rapide pour une rangée de 10 articles, et 3,4 fois plus rapide pour une rangée de 1 000 000 articles.
évidemment, le nombre de comparaisons n'est pas le problème, mais peut-être le nombre de réattributions, et le fait d'appeler une fonction récursive (ce qui pourrait expliquer pourquoi 1.000.000 valeurs s'exécute plus lent que 10 valeurs).
mises en garde : je l'ai fait en VBA, pas en C, et je comparais des nombres de double précision et je retournais l'indice 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 pour le timing haute résolution):
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
après avoir lu la question et les réponses, j'ai décidé d'essayer quelques versions (en C#).
Je pensais que le plus rapide serait celui D'Anton Knyazyev (branche libre),
il n'est pas (ma boite).
Résultats:
/* comp. time(ns)
minmax0 3n/2 855
minmax1 2n 805
minmax2 2n 1315
minmax3 2n 685 */
pourquoi minmax1 et minmax3 sont plus rapides?
Probablement parce que le "prédicteur de branche" fait un bon travail,
chaque itération la chance, un nouveau min (ou max) est trouvé, diminue,
donc les prédictions deviennent meilleures.
Dans l'ensemble c'est un test simple. Je me rends compte que mes conclusions peuvent être:
-prématuré.
- non valide pour les différentes plateformes.
Disons qu'ils sont donnés à titre indicatif.
Modifier: point d'équilibre minmax0, minmax3: ~100 éléments,
10 000 articles: minmax3 ~ 3,5 fois plus rapide que minmax0.
using System;
using sw = System.Diagnostics.Stopwatch;
class Program
{
static void Main()
{
int n = 1000;
int[] a = buildA(n);
sw sw = new sw();
sw.Start();
for (int i = 1000000; i > 0; i--) minMax3(a);
sw.Stop();
Console.Write(sw.ElapsedMilliseconds);
Console.Read();
}
static int[] minMax0(int[] a) // ~3j/2 comp.
{
int j = a.Length - 1;
if (j < 2) return j < 0 ? null :
j < 1 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a[1], ai = a0;
if (a1 < a0) { a0 = a1; a1 = ai; }
int i = 2;
for (int aj; i < j; i += 2)
{
if ((ai = a[i]) < (aj = a[i + 1])) // hard to predict
{ if (ai < a0) a0 = ai; if (aj > a1) a1 = aj; }
else
{ if (aj < a0) a0 = aj; if (ai > a1) a1 = ai; }
}
if (i <= j)
{ if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
return new int[] { a0, a1 };
}
static int[] minMax1(int[] a) // ~2j comp.
{
int j = a.Length;
if (j < 3) return j < 1 ? null :
j < 2 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a0, ai = a0;
for (int i = 1; i < j; i++)
{
if ((ai = a[i]) < a0) a0 = ai;
else if (ai > a1) a1 = ai;
}
return new int[] { a0, a1 };
}
static int[] minMax2(int[] a) // ~2j comp.
{
int j = a.Length;
if (j < 2) return j == 0 ? null : new int[] { a[0], a[0] };
int a0 = a[0], a1 = a0;
for (int i = 1, ai = a[1], aj = ai; ; aj = ai = a[i])
{
ai -= a0; a0 += ai & ai >> 31;
aj -= a1; a1 += aj & -aj >> 31;
i++; if (i >= j) break;
}
return new int[] { a0, a1 };
}
static int[] minMax3(int[] a) // ~2j comp.
{
int j = a.Length - 1;
if (j < 2) return j < 0 ? null :
j < 1 ? new int[] { a[0], a[0] } :
a[0] < a[1] ? new int[] { a[0], a[1] } :
new int[] { a[1], a[0] };
int a0 = a[0], a1 = a[1], ai = a0;
if (a1 < a0) { a0 = a1; a1 = ai; }
int i = 2;
for (j -= 2; i < j; i += 3)
{
ai = a[i + 0]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
ai = a[i + 1]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
ai = a[i + 2]; if (ai < a0) a0 = ai; if (ai > a1) a1 = ai;
}
for (j += 2; i <= j; i++)
{ if ((ai = a[i]) < a0) a0 = ai; else if (ai > a1) a1 = ai; }
return new int[] { a0, a1 };
}
static int[] buildA(int n)
{
int[] a = new int[n--]; Random rand = new Random(0);
for (int j = n; n >= 0; n--) a[n] = rand.Next(-1 * j, 1 * j);
return a;
}
}
un pseudo-code simple pour 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)).
import java.util.*;
class Maxmin
{
public static void main(String args[])
{
int[] arr = new int[10];
Scanner in = new Scanner(System.in);
int i, min=0, max=0;
for(i=0; i<=9; i++)
{
System.out.print("Enter any number: ");
arr[i] = in.nextInt();
}
min = arr[0];
for(i=0; i<=9; i++)
{
if(arr[i] > max)
{
max = arr[i];
}
if(arr[i] < min)
{
min = arr[i];
}
}
System.out.println("Maximum is: " + max);
System.out.println("Minimum is: " + 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);
}
}
public static int[] minMax(int[] array){
int [] empty = {-1,-1};
if(array==null || array.length==0){
return empty;
}
int lo =0, hi = array.length-1;
return minMax(array,lo, hi);
}
private static int[] minMax(int []array, int lo, int hi){
if(lo==hi){
int [] result = {array[lo], array[hi]};
return result;
}else if(lo+1==hi){
int [] result = new int[2];
result[0] = Math.min(array[lo], array[hi]);
result[1] = Math.max(array[lo], array[hi]);
return result;
}else{
int mid = lo+(hi-lo)/2;
int [] left = minMax(array, lo, mid);
int [] right = minMax(array, mid+1, hi);
int []result = new int[2];
result[0] = Math.min(left[0], right[0]);
result[1] = Math.max(left[1], right[1]);
return result;
}
}
public static void main(String[] args) {
int []array = {1,2,3,4,100};
System.out.println("min and max values are "+Arrays.toString(minMax(array)));
}
#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;
}
/ / ceci peut être fait dans la complexité log(n)!!!
il suffit de boucler la boucle sur le tableau une fois, en gardant la trace du max et min jusqu'ici.