Ejemplos

 

El problema consiste en encontrar el máximo de un conjunto de números. Para un ejemplo más complejo véase Algoritmo de Euclides.


Descripción de alto nivel 

Dado un conjunto finito C de números, se tiene el problema de encontrar el número más grande. Sin pérdida de generalidad se puede asumir que dicho conjunto no es vacío y que sus elementos están numerados como

 

c_0,c_1,\dots,c_n

 

 

Es decir, dado un conjunto C=\{c_0,c_1,\dots,c_n\} se pide encontrar m tal que x\leq m para todo elemento x que pertenece al conjunto C.

Para encontrar el elemento máximo, se asume que el primer elemento (c0) es el máximo; luego, se recorre el conjunto y se compara cada valor con el valor del máximo número encontrado hasta ese momento. En el caso que un elemento sea mayor que el máximo, se asigna su valor al máximo. Cuando se termina de recorrer la lista, el máximo número que se ha encontrado es el máximo de todo el conjunto.



Descripción formal 

El algoritmo escrito de una manera más formal, esto es, en pseudocódigo tendría el siguiente aspecto:

 

Algoritmo Encontrar el máximo de un conjunto

función\max(C)\,

//C es un conjunto no vacío de números//
n\gets|C| // | C | es el número de elementos de C//
m\gets c_0
parai\gets 1 hasta n\, hacer
si c_i > m\, entonces
m\gets c_i
devolverm\,

Sobre la notación:

  • "\gets" representa la asignación entre dos objetos. Por ejemplo, m\leftarrow x significa que el objeto m cambia su valor por el de x
  • "devolver" termina el algoritmo y devuelve el valor a su derecha (en este caso, el máximo de C)



Implementación 

En lenguaje C++:

int max(int c[], int n){
int i, m = c[0];

   for (i = 1; i < n; i++)
if (c[i] > m) m = c[i];
return m;
En lenguaje C_Sharp:
static int max(int[] c){
int result=c[0];
for(int i=1;i<c.Length;i++){
if(c[i]>result)

    result=c[i];
return result;

En lenguaje Java:

 public int max( int c[] ) {
int n = c.length, m = c[0];
for( int i = 1 ; i < n ; i++ )
if( c[i] > m ) m = c[i];
return m;
}En lenguaje Visual Basic 8 (2005):
 Public Function max(C As Integer()) As Integer
Dim n As Integer = C.GetLength(0)
Dim m As Integer = C(0)
For i As Integer = 1 To n
If C(i) > m Then
m = C(i)
End If
Next
Return m
End Function
En lenguaje Delphi:
function Max(const ListaNumeros: array of Integer): Integer;
var
vTemp, i: Integer;

begin
vTemp:= 0;
for i:= 1 to High(ListaNumeros) do
if ListaNumeros[i] > vTemp then
vTemp:= ListaNumeros[i];
Result:= vTemp;

end;
En lenguaje Ada
 type T_Conjunto is array <> of Integer;
function Maximo
   (Conjunto : T_Conjunto) return Integer 
is
Temporal : Integer := Conjunto (1);
begin
for I in 2 .. Conjunto'Last loop
if Conjunto (I) > Temporal then
Temporal := Conjunto (I);
end if;
end loop;

    return Temporal;
end Maximo;
En lenguaje Python
def max(c):
n=len(c) m=c[0]
for i in range(1,n):
if c[i]>m: m=c[i]
return m

Análisis 

El algoritmo anterior tiene un orden de eficiencia en tiempo de O(n), en la notación O mayúscula, siendo n el tamaño de la entrada, más concretamente, en este caso, el número de elementos de C. Además, como el algoritmo necesita recordar un único valor (el máximo) requiere un espacio adicional de O(1) (hay que tener en cuenta que el tamaño de las entradas no se considera como memoria usada por el algoritmo).