Cita:
|
Empezado por kalimero
Hola .
Saco el mayor de los primeros 500 y luego el mayor de los restantes 500 y comparo los dos mayores
|
Ajá. Y ¿cómo sacas el mayor de entre 500? Yo digo que revisándolos secuencialmente. ¿No? Ok, ahora divides los 500 en 250. ¿Cómo sacas el mayor de entre 250? Yo digo que revisándolos secuencialente. ¿No? Ok, ahora...
No importa cuántas veces dividas, esencialmente estará revisádolos secuencialmente uno a no.
Y, por ejemplo, un "algoritmo" como éste para encontar el máximo de entre N números:
Código:
Max := A[1]
FOR I := 2 TO N do
IF Max < A[i] then Max := A[i]
será de orden o(n).
Si sacas primero el mayor entre una mitad y otra y comparas ambos, cad parte será de orde o(n) y la suma será entonces de orde o(n).
// Saludos