Upload
vicedo99
View
38
Download
4
Embed Size (px)
Citation preview
TEMA 2 LA EFICIENCIA DE LOS ALGORITMOS
Departamento de Lenguajes y Sistemas Informáticos
UNIVERSIDAD DE ALICANTE
LOS ALGORITMOS
La eficiencia de los algoritmosOBJETIVOS
Proporcionar la capacidad para analizar con rigor la eficiencia de los algoritmos
Distinguir los conceptos de eficiencia en tiempo y en espacioIntroducir las bases matemáticas para poder aplicar el criterio asintótico a los conceptos de eficienciaCalcular la complejidad temporal o espacial de un algoritmo
2
Calcular la complejidad temporal o espacial de un algoritmo recursivo o iterativoComparar, respecto a eficiencia, distintas soluciones algorítmicas a un mismo problema
La eficiencia de los algoritmosCONTENIDO
1. Noción de complejidad2. Cotas de complejidad3. Análisis asintótico4. Cálculo de complejidades
Algoritmos Iterativos
3
Algoritmos Recursivos. Ecuaciones de recurrencia5. Anexo
1. Noción de complejidad¿QUÉ ES UN ALGORITMO?
Un algoritmo es una serie finita de pasos que expresa una forma o estrategia de resolución de un problema.Importante:
El número de pasos debe ser finito. El algoritmo debe terminar en un tiempo finito.El algoritmo debe ser capaz de determinar la solución del
4
El algoritmo debe ser capaz de determinar la solución del problema. Se trata de un método sistemático, susceptible de ser realizado mecánicamente, para resolver un problema dado.
1. Noción de complejidadDEFINICIÓN
Complejidad de un algoritmoMedida de los recursos que un algoritmo necesita para su ejecuciónComplejidad temporal: Tiempo que un algoritmo necesita para su ejecuciónComplejidad espacial: Recursos espaciales (de almacén) que un
5
Complejidad espacial: Recursos espaciales (de almacén) que un algoritmo consume o necesita para su ejecución
Posibilidad de hacerValoraciones: el algoritmo A es “bueno”, “el mejor”, “prohibitivo”Comparaciones: el algoritmo A es mejor que el B
Nos centraremos en el estudio de la complejidad temporal
1. Noción de complejidadCOMPLEJIDAD TEMPORAL
El tiempo de ejecución de un algoritmo depende de:Factores externos
La máquina en la que se va a ejecutarEl compiladorLa experiencia del programadorLos datos de entrada suministrados en cada ejecución
6
jInternos
El número de instrucciones asociadas al algoritmo
¿Cómo estudiamos el tiempo de ejecución de un algoritmo?
1. Noción de complejidad¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
Análisis empírico (a posteriori):Generando ejecuciones del algoritmo para distintos valores de entrada y cronometrando el tiempo de ejecuciónJ Se obtiene una medida real del comportamiento del algoritmo en el entorno de
aplicaciónL El resultado depende de los factores externos e internos
7
Análisis analítico (a priori):Obtener una función que represente el tiempo de ejecución del algoritmo para cualquier valor de entradaJ El resultado depende sólo de los factores internosJ Estima el comportamiento del algoritmo de forma independiente de los
factores externosJ No es necesario implementar y ejecutar los algoritmos L No obtiene una medida real del comportamiento del algoritmo en el entorno de
aplicación
Ambas medidas son importantes
1. Noción de complejidad¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
Se expresa mediante funciones de coste. Permiten determinar el comportamiento de un algoritmo para cualquier entrada posible.Las entradas se expresan mediante lo que denominamos talla, tamaño de la entrada o tamaño del problema.
Talla o tamaño de un problema:
8
Talla o tamaño de un problema:Valor o conjunto de valores asociados a la entrada del problema que representa una medida de su tamaño respecto de otras entradas posibles
Denotaremos T(n) al tiempo de ejecución de un algoritmo para una entrada de tamaño n.
1. Noción de complejidad ¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
¿Qué unidad de medida empleamos para T(n)?¿segundos? No existe unidad concretaNo existe ordenador de referencia para estas medidas
El principio de InvarianzaDado un algoritmo y dos implementaciones I1 e I2 (máquinas o códigos distintos) que tardan en ejecutarse T (n) y T (n) entonces
9
distintos) que tardan en ejecutarse T1(n) y T2(n) , entonces
Es decir, el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado va a diferir como mucho en una constante multiplicativaPor tanto podemos decir que un algoritmo tarda un tiempo del orden deT(n) si y una implementación I del algoritmo que tarda menos que c ·T(n) para cualquier entrada de tamaño n
0 0 1 2, / ( ) · ( )c n n n T n c T n+∃ ∈ ∃ ∈ ∀ ≥ ≤
c +∃ ∈
1. Noción de complejidad ¿CÓMO ESTUDIAMOS EL TIEMPO DE EJECUCIÓN?
¿Unidad en función del tipo de análisis?Análisis empírico (a posteriori):
Emplearemos los segundos siempre que se particularice el estudio a la ejecución de una implementación concreta de un algoritmo en una máquina determinada
Análisis analítico (a priori):
10
Necesitamos definir una unidad de medida teórica, independiente de factores externosSe define una unidad de medida (operación elemental o paso de programa) El tiempo de un algoritmo se puede así medir como el número de pasos de programa que realiza para una entrada dada.
1. Noción de complejidad CONSIDERACIONES
¿Porqué es importante conocer el coste de ejecución de los algoritmos? ¿Porqué se emplean funciones de coste para expresar el coste de un algoritmo?¿Cómo definimos un paso de programa u operación elemental? ¿Cómo lo identificamos en un algoritmo?
11
¿Cómo lo identificamos en un algoritmo?
1. Noción de complejidad CONSIDERACIONES
¿Porqué es importante conocer el coste de ejecución de los algoritmos?Ejemplo: El cuadrado de un número concreto (1000)
f i C ad1() t
1 Paso de programa = 1operación simple
12
• Diferente coste según algoritmo
• Todos coste constante
funcion Cuad1():entero;devuelve(1000*1000); // 2 //
fin /* 2 */
funcion Cuad2():entero;m=0; // 1 //para i=1 hasta 1000 // 1001+1001 //
m=m+1000; // 1000+1000 //fparadevuelve(m); // 1 //
fin /* 4004 */
Número total de operaciones
1. Noción de complejidadCONSIDERACIONES
¿Porqué se emplean funciones de coste para expresar el coste de un algoritmo?
Necesitamos que la expresión del coste del algoritmo sea válida para cualquier entrada al mismo (se expresa en función de su talla)
Ejemplo: El cuadrado de un número cualquiera (n)
13
funcion Cuad3(n:ent):entero;devuelve(n*n); // 2 //
Fin /* 2 */
funcion Cuad4(n:ent):entero;m=0; // 1 //para i=1 hasta n // n+1+n+1 //
m=m+n; // n+n //fparadevuelve(m); // 1 //
fin /* 4n+4 */
• Diferente coste según algoritmo• Primero: coste constante (No depende de n)• Segundo: coste variable en función de n (talla del problema)
( ) 2f n =
( ) 4 4f n n= +
1. Noción de complejidad CONSIDERACIONES
Talla o tamaño de un problema:Valor o conjunto de valores asociados a la entrada del problema que representa una medida de su tamaño respecto de otras entradas posiblesCuad3: - Cuad4:( ) 2f n = ( ) 4 4f n n= +
14
010203040506070
1 5 10 15tamaño problema
tiem
po
f(n)=2f(n)=4n+4
1. Noción de complejidadCONSIDERACIONES
¿Cómo definimos un paso de programa u operación elemental? ¿Cómo lo identificamos en un algoritmo?Paso de programa:
Secuencia de operaciones con contenido semántico cuyo coste es independiente de la talla del problema.Ejemplo:
15
Ejemplo:Opción A: 1 Paso = operación simpleOpción B: 1 Paso = secuencia máxima de operaciones cuyo coste es independiente de la talla del problema
func SUMAR(A:vector[1..n]:ent):ent;(1) s=0(2) para i=1 hasta n hacer(3) s=s+A[i]; Imprime(A[i]);
fpara(4) devuelve(s); fin
Línea Opcion-A Opcion-B(1) 1 1(2) (n+1)(1+1)(3) (n+1)(1+1+1)
(4) 1 1 Suma 5n+7 n+2
n (1)
¿Cuál es la diferencia?
1. Noción de complejidadCÁLCULO DEL NÚMERO DE PASOS DE PROGRAMA
Una operación elemental corresponde a un paso de programa. La complejidad de una secuencia consecutiva de instrucciones se calcula sumando los pasos de cada una de las instruccionesEstructuras de selección. El tiempo de ejecución de la sentencia “SI C ENTONCES S1 SINO S2 FINSI” es:
( ) { ( 1) ( 2)}T T C T S T S
16
Estructuras repetitivas. El tiempo de ejecución de un bucle “MIENTRAS C HACER S FIN” es:
donde T(C) y T(S) pueden variar en cada iteración, y por tanto habrá que tenerlo en cuenta para su cálculo.El resto de sentencias iterativas se asemeja al bucle MIENTRAS
( ) max{ ( 1), ( 2)}T T C T S T S= +
( ) ( º ) *( ( ) ( ))T T C n iteraciones T S T C= + +
1. Noción de complejidadCÁLCULO DEL NÚMERO DE PASOS DE PROGRAMA
Funciones: El tiempo de ejecución de una llamada a un procedimiento o función F(P1, P2,..., Pn) es 1 (por la llamada), más el tiempo de evaluación de los parámetros P1, P2,..., Pn, más el tiempo que tarde en ejecutarse F, esto es:
1 2 1 ( ) ( ) ... ( ) ( )nT T P T P T P T F= + + + + +
17
El paso de parámetros por referencia, por tratarse simplemente de punteros, no contabilizaEl tiempo de ejecución de las llamadas a procedimientos recursivos va a dar lugar a ecuaciones en recurrencia, que veremos posteriormente.
1. Noción de complejidadEJERCICIOS
funcion ejemplo1 (n:entero):entero;
n=n+1;devuelve(n);
fin
18
funcion ejemplo2 (n:entero):entero;i=0;mientras (i ≤ 2000)
n=n+1;i=i+1;
fmientras;devuelve(n);
fin
1. Noción de complejidadEJERCICIOS
funcion ejemplo3 (n:entero):entero;
j = 2;para i = 1 hasta 2000
j=j*j;fpara;i = 0;
19
i 0;mientras (i ≤ n)
j = j + j;j = j - 2;i = i + 1;
fmientras;devuelve(j);
fin
1. Noción de complejidadEJERCICIOS
funcion ejemplo4 (n:entero):entero;k = 1;para i=0 hasta n
para j=1 hasta nk = k + k;
finparafinpara
20
funcion ejemplo5 (n:entero):entero;k = 1;para i=0 hasta n
para j=i hasta nk = k + k;
finparafinparadevuelve(k);
fin
finparadevuelve(k);
fin
Cálculo de la traspuesta de una matriz
1. Noción de complejidadEJERCICIOS
función TRASPUESTA (var A:matriz) var i,j,filas: entero fvar
filas=numfilas (A);para i=1 hasta filas-1 hacer
para j=i+1 hasta filas hacerb [j i]
21
b=A[j,i];A[j,i]=A[i,j];A[i,j]=b;
fparafpara
fin
Producto de dos matrices
1. Noción de complejidadEJERCICIOS
función PRODUCTO (var A,B:matriz; n,m:entero):matrizvar C:matriz; i,j,k,suma:entero fvar
para i=1 hasta n hacerpara j=1 hasta n hacer
suma=0;para k 1 hasta m hacer
22
para k=1 hasta m hacersuma= suma + Ai,k * Bk,j;
fparaCi,j=suma;
fparafparadevuelve C;
fin
2. Cotas de complejidad INTRODUCCION
Dado un vector X de n números naturales y dado un número natural zEncontrar el índice i tal que Xi = zCalcular el número de pasos que realiza
función BUSCAR (var X:vector[N]; z:N):devuelve N;var i:natural fvar;
i 1
23
i=1;mientras (i≤⏐X⏐) ∧ (Xi≠z) hacer
i=i+1;fmientrassi (i=⏐X⏐+1) entonces devuelve(0) (*No encontrado*)
si_no devuelve(i)fin
2. Cotas de complejidad EL PROBLEMA
No podemos contar el número de pasos porque para diferentes entradas de un mismo tamaño de problema se obtienen diferentes complejidadesEjemplo:
X z Nº PASOS ( )
24
¿Qué podemos hacer?Acotar el coste mediante dos funciones que expresen respectivamente, el máximo y el mínimo coste del algoritmo (cotas de complejidad)
( 1, 0, 2, 4 ) 3 1 + 5 + 1 = 7( 1, 0, 2, 4 ) 0 1 + 2 + 1 = 4 ( 1, 0, 2, 4 ) 1 1 + 1 + 1 = 3
2. Cotas de complejidadLA SOLUCIÓN: Cotas de complejidad
Cuando aparecen diferentes casos para una misma talla genérica n, se introducen las cotas de complejidad
Caso peor: cota superior del algoritmo → Cs(n)Caso mejor: cota inferior del algoritmo → Ci(n)Caso promedio: cota promedio → Cm(n)
25
Todas son funciones del tamaño del problemaLa cota promedio es difícil de evaluar a priori
Es necesario conocer la distribución de probabilidad de la entradaNo es la media de la inferior y de la superior
2. Cotas de complejidadEJEMPLO: Cotas superior e inferior
función BUSCAR (var X:vector[N]; z:N):devuelve Nvar i: natural fvar;(1) i=1;(2) mientras (i≤⏐X⏐) ∧ (Xi≠z) hacer(3) i=i+1;
fmientras(4) si i= ⏐X⏐+1 entonces devuelve 0 si_no devuelve ifi
26
fin
Línea Mejor Caso Peor Caso (1) 1 1(2,3) 1 n(4) 1 1Suma 3 n+2
Tamaño del problema (n)= Número de elementos del vector X (⏐X⏐)
Cs(n)=n+2Ci (n)=3
2. Cotas de complejidad EJEMPLO: Cotas superior e inferior
Complejidad función Buscar
141618
Ci(n)=3Cs(n)=n+2
Cota Superior
27
02468
101214
1 5 10 15Cota Inferior
¿Cota promedio?
3. Análisis asintóticoINTRODUCCION
El estudio de la complejidad resulta realmente interesante para tamaños grandes de problema por varios motivos:
Las diferencias “reales” en tiempo de ejecución de algoritmos con diferente coste para tamaños pequeños de problema no suelen ser muy significativasEs lógico invertir tiempo en el desarrollo de un buen algoritmo sólo si se
28
g p gprevé que éste realizará un gran volumen de operaciones
Al estudio de la complejidad para tamaños grandes de problema se le denomina análisis asintótico
Permite clasificar las funciones de complejidad de forma que podamos compararlas entre si fácilmentePara ello, se definen clases de equivalencia que engloban a las funciones que “crecen de la misma forma” (ver principio de invarianza).Se emplea la notación asintótica
3. Análisis asintótico NOTACION ASINTÓTICA
Notación matemática utilizada para representar la complejidad cuando el tamaño de problema (n) es muy grande (n →∞)Se definen tres tipos de notación
Notación O (big-omicron) ⇒ Cota superiorNotación Ω (omega) ⇒ Cota inferiorN t ió Θ (bi th t ) C t di
29
Notación Θ (big-theta) ⇒ Cota promedio
3. Análisis asintóticoCOTA SUPERIOR. NOTACION O
Sea se define el conjunto O(f) como el conjunto de funciones acotadas superiormente por un múltiplo de f :
Dada una función se dice que si existe un múltiplo de f que es cota superior de t
0:f ≥→
{ }00 0( ) : | 0, / g( ) · ( )f g c n n n n c f n≥Ο = → ∃ > ∃ ∈ ∀ ≥ ≤
0:t ≥→ ( )t f∈Ο
30
múltiplo de f que es cota superior de t
Sea se define el conjunto O(f) como el conjunto de funciones acotadas superiormente por un múltiplo de f :
Dada una función se dice que si existe un múltiplo de f que es cota superior de t
0:f ≥→
{ }00 0( ) : | 0, / g( ) · ( )f g c n n n n c f n≥Ο = → ∃ > ∃ ∈ ∀ ≥ ≤
0:t ≥→ ( )t f∈Ο
3. Análisis asintóticoCOTA SUPERIOR. NOTACION O
31
múltiplo de f que es cota superior de t
( )t n
· ( )c f n
Ejemplos:
3n + 1 ¿pertenece a O(n) ?3n2 + 1 ¿pertenece a O(n) ?3n2 + 1 ¿pertenece a O(n2)?
3. Análisis asintótico NOTACION O : PROPIEDADES
Veamos algunas propiedades de esta notación:1. Dada una función f, entonces 2.
3.
¿Para qué sirven?Nos permiten agrupar en clases aquellas funciones con el mismo crecimiento
( )f f∈Ο( ) ( ) ( )f g f g∈Ο ⇒Ο ⊂ Ο
( ) ( ) ( ) ( )f g f g g fΟ = Ο ⇔ ∈Ο ∧ ∈Ο
32
p g p qEjemplo:
¿ O(3n) = O(15n) ?¿ O(349n2) = O(2n2) ?
Las clases resultantes se representan con la función más simple que contienenEjemplo:
O(3n) = O(15n) - Representante : O(n)O(349n2) = O(2n2) - Representante : O(n2)
3. Análisis asintótico NOTACION O : PROPIEDADES
Veamos algunas propiedades de esta notación:1. Dada una función f, entonces 2.
3.
¿Para qué sirven?Nos permiten agrupar en clases aquellas funciones con el mismo crecimiento
( )f f∈Ο( ) ( ) ( )f g f g∈Ο ⇒Ο ⊂ Ο
( ) ( ) ( ) ( )f g f g g fΟ = Ο ⇔ ∈Ο ∧ ∈Ο
33
p g p q
3. Análisis asintótico NOTACION O : MAS PROPIEDADES
Veamos más propiedades interesantes de esta notación:
4.
5.
6. Regla de la suma: 7. Regla del producto:
( ) ( ) ( )f g g h f h∈Ο ∧ ∈Ο ⇒ ∈Ο( ) ( ) (min( , ))f g g h f g h∈Ο ∧ ∈Ο ⇒ ∈Ο
1 1 2 2 1 2 1 2Si ( ) ( ) (max( , ))f g f g f f g g∈Ο ∧ ∈Ο ⇒ + ∈Ο
1 1 2 2 1 2 1 2Si ( ) ( ) · ( · )f g f g f f g g∈Ο ∧ ∈Ο ⇒ ∈Ο
34
8.
9.
10.
1 1 2 2 1 2 1 2( ) ( ) ( )f g f g f f g g
( )lim 0 ( )( )n
f n f gg n→∞
= ⇒ ∈Ο
-1-1 1 0( ) · · ... · ( )m m m
m mf n a n a n a n a n= + + + + ∈Ο
( ) ( ) ( ) ( )f g f g g fΟ ⊂ Ο ⇔ ∈Ο ∧ ∉Ο
3. Análisis asintóticoCOTA INFERIOR. NOTACION Ω
Sea se define el conjunto Ω(f) como el conjunto de funciones acotadas inferiormente por un múltiplo de f :
Dada una función se dice que si existe un múltiplo de f que es cota inferior de t
0:f ≥→
{ }00 0( ) : | 0, / g( ) · ( )f g c n n n n c f n≥Ω = → ∃ > ∃ ∈ ∀ ≥ ≥
0:t ≥→ ( )t f∈Ω
35
múltiplo de f que es cota inferior de t
3. Análisis asintóticoCOTA INFERIOR. NOTACION Ω
Sea se define el conjunto Ω(f) como el conjunto de funciones acotadas inferiormente por un múltiplo de f :
Dada una función se dice que si existe un múltiplo de f que es cota inferior de t
0:f ≥→
{ }00 0( ) : | 0, / g( ) · ( )f g c n n n n c f n≥Ω = → ∃ > ∃ ∈ ∀ ≥ ≥
0:t ≥→ ( )t f∈Ω
36
múltiplo de f que es cota inferior de t
( )t n
· ( )c f n
Ejemplos:
3n + 1 ¿pertenece a Ω(n) ?3n2 + 1 ¿pertenece a Ω(n) ?3n2 + 1 ¿pertenece a Ω(n2)?
3. Análisis asintótico NOTACION Ω : PROPIEDADES
Veamos algunas propiedades de esta notación:1. Dada una función f, entonces 2.
3.
4.
5.
( )f f∈Ω( ) ( ) ( )f g f g∈Ω ⇒Ω ⊂Ω
( ) ( ) ( ) ( )f g f g g fΩ = Ω ⇔ ∈Ω ∧ ∈Ω( ) ( ) ( )f g g h f h∈Ω ∧ ∈Ω ⇒ ∈Ω( ) ( ) (max( , ))f g g h f g h∈Ω ∧ ∈Ω ⇒ ∈Ω
37
6. Regla de la suma: 7. Regla del producto:
8.
9.
( ) ( ) ( ( , ))f g g f g1 1 2 2 1 2 1 2Si ( ) ( ) ( )f g f g f f g g∈Ω ∧ ∈Ω ⇒ + ∈Ω +1 1 2 2 1 2 1 2Si ( ) ( ) · ( · )f g f g f f g g∈Ω ∧ ∈Ω ⇒ ∈Ω
( )lim 0 ( )( )n
f n g fg n→∞
= ⇒ ∈Ω
-1-1 1 0( ) · · ... · ( ) si 0m m m
m m mf n a n a n a n a n a= + + + + ∈Ω >
3. Análisis asintóticoCOTA PROMEDIO. NOTACION Θ
Sea se define el conjunto Θ(f) como el conjunto de funciones acotadas superior e inferiormente por un múltiplo de f :
O lo que es lo mismo: Dada una función se dice que si existen
0:f ≥→
{ }00 0( ) : | , 0, / · ( ) g( ) · ( )f g c d n n n c f n n d f n≥Θ = → ∃ > ∃ ∈ ∀ ≥ ≤ ≤
0t ≥ ( )t f∈Θ( ) ( ) ( )f f fΘ = Ο ∩Ω
38
Dada una función se dice que si existen múltiplos de f que son cota superior y cota inferior de t
0:t ≥→ ( )t f∈Θ
3. Análisis asintóticoCOTA PROMEDIO. NOTACION Θ
Sea se define el conjunto Θ(f) como el conjunto de funciones acotadas superior e inferiormente por un múltiplo de f :
O lo que es lo mismo: Dada una función se dice que si existen
0:f ≥→
{ }00 0( ) : | , 0, / · ( ) g( ) · ( )f g c d n n n c f n n d f n≥Θ = → ∃ > ∃ ∈ ∀ ≥ ≤ ≤
0t ≥ ( )t f∈Θ( ) ( ) ( )f f fΘ = Ο ∩Ω
39
Dada una función se dice que si existen múltiplos de f que son cota superior y cota inferior de t
0:t ≥→ ( )t f∈Θ
( )t n
· ( )c f n
· ( )d f nEjemplos:
3n + 1 ¿pertenece a Θ(n) ?3n2 + 1 ¿pertenece a Θ(n) ?3n2 + 1 ¿pertenece a Θ(n2)?
3. Análisis asintóticoNOTACION Θ : PROPIEDADES
Veamos algunas propiedades de esta notación:1. Dada una función f, entonces 2.
3.
4.
5. Regla de la suma:
( )f f∈Θ( ) ( ) ( )f g f g∈Θ ⇒Θ = Θ
( ) ( ) ( ) ( )f g f g g fΘ = Θ ⇔ ∈Θ ∧ ∈Θ( ) ( ) ( )f g g h f h∈Θ ∧ ∈Θ ⇒ ∈Θ
1 1 2 2 1 2 1 2Si ( ) ( ) (max( , ))f g f g f f g g∈Θ ∧ ∈Θ ⇒ + ∈Θ
40
6. Regla del producto: 7.
8.
1 1 2 2 1 2 1 2( ) ( ) ( ( , ))f g f g f f g g1 1 2 2 1 2 1 2Si ( ) ( ) · ( · )f g f g f f g g∈Θ ∧ ∈Θ ⇒ ∈Θ
( )lim /( 0 ) ( ) ( )( )n
f n k k k f gg n→∞
= ≠ ∧ ≠ ∞ ⇒Θ = Θ
-1-1 1 0( ) · · ... · ( ) si 0m m m
m m mf n a n a n a n a n a= + + + + ∈Θ >
Los conjuntos de funciones están incluidos unos en otros generando una ordenación de las diferentes funciones
3. Análisis asintóticoJERARQUIA DE FUNCIONES
1( ( ))f nΟ 2( ( ))f nΟ 3( ( ))f nΟ
41
Las clases más utilizadas en la expresión de complejidades son: 1
2 2
(1) (lglg ) (lg ) (lg )
( ) ( ) ( lg )
( ) ( ) (2 ) ( !) ( )
a
a n n
n n n
n O n n n
n n n n
>
>
Ο ⊂Ο ⊂Ο ⊂Ο ⊂
⊂Ο ⊂ ⊂Ο ⊂
⊂Ο ⊂ ⊂Ο ⊂Ο ⊂Ο ⊂Ο
constantes sublogarítmicas logarítmicas
sublineales lineales lineal-logarítmicas
polinómicas exponenciales
¿Cuál es la diferencia real entre complejidades?Ejemplo: Máximo tamaño, por hora, que pueden resolver algoritmos cuyo tiempo de ejecución está acotado superiormente por algunas de las funciones anteriores.
La complejidad logarítmica es mucho mejor que la lineal. No requiere mucho esfuerzo
3. Análisis asintóticoJERARQUIA DE FUNCIONES
Complejidad 1 paso=1 ms. 1 paso=0’1 ms.
42
q qplantear soluciones logarítmicas a problemas aparentemente lineales (p.e. la búsqueda de un elemento en un vector ordenado).Ante una complejidad elevada no tiene sentido invertir en hardware para acelerar el tiempo de proceso.
log n 10106 10107
n 3’6 ⋅ 106 3’6 ⋅ 107
n log n 2 ⋅ 105 2 ⋅ 106
n2 1.897 6000
n3 153 330
2n 21 25
3. Análisis asintóticoEJERCICIOS
1..1 1
1. ( ) O( ( )) ( ) O( ( )) ( ) O( ( ))
2. ( ( )) O( ( )) ( ) O( ( )) ( ) O( ( ))
3. ( ) O( ( )) ( ) O ( )k k
i i k i ii i
f n g n g n h n f n h n
f n g n f n g n g n f n
f n g n f n g n= =
∈ ∧ ∈ ⇔ ∈
Ο = ⇔ ∈ ∧ ∈
⎛ ⎞∈ ⇒ ∈ ⎜ ⎟
⎝ ⎠∏ ∏
43
1.. 11
4. ( ) O( ( )) ( ) O max ( )
5. ( ) O(
i i
k k
i i k i iii
i i
f n g n f n g n
f n g
==
⎝ ⎠
⎛ ⎞∈ ⇒ ∈ ⎜ ⎟⎝ ⎠
∈
∑
1..1 1
1
1
( )) ( ) O ( )
6. O(lg ) O(lg ) , 1
7. O( )
k k
k i ii i
a b
nk k
i
n f n g n
n n a b
i n
= =
+
=
⎛ ⎞⇒ ∈ ⎜ ⎟⎝ ⎠
= ∀ >
∈
∑ ∑
∑
4. Calculo de ComplejidadesINTRODUCCION
Cálculo de la complejidad espacial y temporalNos centraremos en la complejidad temporalEtapas para obtener las cotas de complejidad1. Determinar la talla o tamaño del problema2. Determinar el caso mejor y peor: instancias para las que el algoritmo
t d á
44
tarda más o menosNo siempre existe mejor y peor caso ya que existen algoritmos que se comportan de igual forma para cualquier instancia del mismo tamaño
3. Obtención de las cotas para cada casoAlgoritmos iterativosAlgoritmos recursivos
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS
La talla es n y no existe caso mejor ni peor.
función SUMAR (A:vector[1..n]:entero):entero;(1) s=0;(2) para i=1 hasta n hacer(3) s=s+A[i]; Imprime(A[i]);
fpara(4) devuelve(s); fin
45
Línea Pasos C. Asintótica(1) 1 Θ(1) (2,3) n(1) Θ(n)(4) 1 Θ(1)Suma n+2 Θ(n)
Correlación entre ambas expresiones
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS
función BUSCAR (var X:vector[N]; z:N):Nvar i:natural fvar;(1) i=1;(2) mientras (i≤⏐X⏐) ∧ (Xi≠z) hacer(3) i=i+1;
fmientras(4) si i= ⏐X⏐+1 entonces devuelve 0 si_no devuelve ifin
46
Línea Cuenta Pasos C.AsintóticaMejor Peor Mejor PeorCaso Caso Caso Caso
(1) 1 1 Ω(1) Ο(1)(2,3) 1 n Ω(1) Ο(n)(4) 1 1 Ω(1) Ο(1)Suma 3 n+2 Ω(1) Ο(n)
Cs(n)=n+2Ci (n)=3
Cs(n)=Ο(n)Ci (n)=Ω(1)
• La talla es el número de elementos del vector (n)• Existe mejor y peor caso ¿cuándo se produce cada uno de ellos?
fin
Cálculo del máximo de un vector
función MÁXIMO (var v:vector[n]):enterovar i,n,max: entero fvar
n=|v|;max=v[1];para i=2 hasta n hacer
i [i] [i] f i
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
47
si v[i]>max entonces max=v[i] fsifparadevuelve max;
fin
función BUSCA (var v:vector[N]; x,pri,ult:natural):naturalvar m:natural fvar
repetirm= (pri+ult)/2;
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
Búsqueda de un elemento en un vector ordenado
48
si v[m]>x entonces ult= m-1si_no pri= m+1
fsihasta (pri>ult) ∨ v[m]=x;si v[m]=x entonces devuelve m
si_no devuelve 0fsi
fin
función F1 (a,n:entero)var i,j:natural fvar
para i=1 hasta n hacerpara j=i hasta 2 hacer (*decreciente*)
F2(a);fpara
fparafin
F2 ∈ Θ(a2)
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
49
función SEP (x,y:entero):enterovar i,j,r:natural fvar
para i=0 hasta (x+y) hacerj=i;mientras (j≠0) hacer
j=j div 2;r=r+j;
fmientrasfparadevuelve r;
fin
función EJEMPLO (var X:vector[carácter]);var i,j,n:natural fvar
n=|X|;i=2;mientras (n>1) ∧ (i≤n) hacer
j=i;
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
50
j i;mientras X[j] ≠ X[1] hacer
j=j div 2;fmientrasi=i+1;
fmientrasfin
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
función CALC (var v:vector[natural);var i,j,n,x:natural fvar
n=|v|;si n>0 entonces
j=n; x=0;mientras x<100 hacer
51
j=j div 2; x=0; i=j;repetir
i=i+1;x=x+v[i];
hasta i=n;si j=0 entonces x=100 fsi
fmientrasImprimir(j);
fsifin
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
funcion PICO (n,m:N):Nvar i,j,x:N;x=0;si (n<=m) entonces
i=n;repetir
52
repetirpara j=1 hasta m*m hacer
x=x+1 fpara;i=i+2;
hasta (i>m);finsi;devuelve x;
fin
4. Calculo de ComplejidadesALGORITMOS ITERATIVOS. EJERCICIOS
función ECTO(a: vector[N]; n:N): enterovar i,j:N; permuta:bool;permuta=CIERTO;i=1;mientras (permuta) hacer
i=i+1;
53
permuta=FALSO;para j=n hasta i hacer
si (a[j]<a[j-1]) entoncesx=a[j];permuta=CIERTO;a[j]=a[j-1];a[j-1]=x;
fsifpara
fmientrasfin
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
Dado un algoritmo recursivo:función factorial (n:entero):entero
si n=1 entonces devuelve(1)si_no devuelve(n*factorial(n-1))
fsifin
54
Podemos obtener el coste de la mayoría de las instrucciones pero, ¿cuál es la contribución al coste total del algoritmo de cada una de las llamadas recursivas?Sólo se puede asegurar que el coste será una función del tamaño del problema f(n) cuyo valor dependerá del coste de las sucesivas llamadas recursivas.
(1) 1( )
(1) ( 1) 1n
f nf n n
Θ ≤⎧= ⎨Θ + − >⎩
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
Una relación de recurrencia es una expresión que relaciona el valor de una función f definida para un entero n con uno o más valores de la misma función para valores menores que n.
0· ( ( )) ( )( )
'( )a f F n P n n n
f n+ >⎧
= ⎨
55
0
( )'( )
fP n n n⎨ ≤⎩
constante ( ), '( ) Funciones de . No tienen por que ser polinomios
- ( ) Función estrictamente decreciente con . Normalmente
/
aP n P n n
n bF n n n b
n b
• ∈•
⎧• < ∈⎨
⎩
Las ecuaciones de recurrencia se usan para expresar la complejidad de un algoritmo recursivo aunque también son aplicables a los iterativosSi el algoritmo dispone de mejor y peor caso, habrá una función para cada casoLa complejidad de un algoritmo se obtiene en tres pasos:1. Determinar la talla del algoritmo
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
56
2. Obtención de las ecuaciones de recurrencia del algoritmo3. Resolución de las ecuaciones
Para resolverlas, usaremos el método de sustitución:Es el método más sencilloSólo para funciones lineales (sólo una vez en función de sí mismas)Consiste en sustituir cada f(n) por su valor al aplicarle de nuevo la función hasta obtener un término general
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
Ejemplo: Calcular la complejidad del siguiente algoritmofunción máximo (a:vector[enteros];n:entero):entero
si n=1 entonces devuelve(a[1])si_no
para j=1 hasta n ESCRIBIR(a[j]) fparadevuelve(MAYOR(máximo(a,n-1),a[n]))
fsifi
ESCRIBIR ∈ Θ(1)
57
1. Obtener talla (n) del algoritmo (n= Num. de elementos del vector) 2. Obtener ecuación de recurrencia a partir del algoritmo
fin MAYOR ∈ Θ(1)
Coste base de recurrencia (NO hay recursión)
Coste caso general de recurrencia (hay recursión)
Coste llamada recursiva
Coste instrucciones no recursivas
(1) 1( )
( ) ( 1) 1n
f nn f n n
Θ =⎧= ⎨Θ + − >⎩
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
Ejemplo: Calcular la complejidad del siguiente algoritmo1. Obtener talla (n) del algoritmo (n= Num. de elementos del vector) 2. Obtener ecuación de recurrencia a partir del algoritmo3. Resolver la recurrencia por sustitución
( ) ( 1) (1ª rec)
( 1) ( 2) (2ª )
f n n f n
f
= + − =
58
La recursión termina cuando (n-i)=1Por tanto, habrá i=n-1 llamadas recursivas
1
0
( 1) ( 2) (2ª rec)
( 1) ( 2) ( 3) ... (3ª rec)
( ) ( ) (i-esima rec)i
j
n n f n
n n n f n
n j f n i−
=
= + − + − =
= + − + − + − =
= − + −∑
1 2
0 0
2 2
0 0
( ) ( ) ( ) ( ) (1)
( 2)( 1)( ) ( ) (1) ( 1) 12
i n
j j
n n
j j
f n n j f n i n j f
n nn j f n n
− −
= =
− −
= =
= − + − = − +
− −= − + = − − +
∑ ∑
∑ ∑
2( ) ( )f n n⇒ ∈Θ
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
QUICKSORTElemento pivote: Nos sirve para dividir en dos partes el vector
Al azarPrimer elemento → Quicksort primer elementoElemento central → Quicksort centralElemento mediana → Quicksort mediana
59
Pasos:Elección del pivoteSe hacen dos recorridos del vector: ascendente (i) y descendente (j)El vector queda dividido en dos partes:
parte izquierda del pivote → elementos menores parte derecha del pivote → elementos mayores
Se hacen dos llamadas recursivas. Una con cada parte del vector.
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
QUICKSORT primer elemento
funcion QUICKSORT_CENTINELA (var a:vector; pi,pf:indice)var i,j: indice; x: elemento fvar
si pi<pf entoncesx=a[pi]; i=pi+1; j=pf;
60
repetirmientras a[i]<x hacer i=i+1 fmientrasmientras a[j]>x hacer j=j-1 fmientrassi i≤j entonces
SWAP(a[i],a[j]); i=i+1; j=j-1;fsi
hasta i>j;SWAP(a[pi],a[j]);QUICKSORT_CENTINELA (a,pi,j-1);QUICKSORT_CENTINELA (a,j+1,pf);
fsifin
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
QUICKSORT Tamaño del problema: nMejor caso: subproblemas (n/2, n /2)
(1) 1( )
nf n
Θ ≤⎧⎪= ⎨ ⎛ ⎞ ⎛ ⎞
61
Peor caso: subproblemas (0, n -1),(n -1,0)
( ) ( ) 1
2 2f n n nn f f n
= ⎨ ⎛ ⎞ ⎛ ⎞Θ + + >⎜ ⎟ ⎜ ⎟⎪ ⎝ ⎠ ⎝ ⎠⎩
( ) ( )(1) 1
( ) ( ) 0 1 1
nf n
n f f n nΘ ≤⎧
= ⎨Θ + + − >⎩
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
QUICKSORTResolución recurrencia mejor caso
( )( ) 2 ( ) (1ª rec)2
2 2 ( ) 2 4 ( ) = (2ª rec)2 4 4
nf n n f
n n nn f n f
= + =
= + + = +
62
La recursión termina cuando (n/2 i)=1Por tanto, habrá i=log2 n llamadas recursivas
( )2 4 2 ( ) 3 8 ( ) ... (3ª rec)4 8 8
2 ( ) 2i
i
n n nn f n f
nin f
= + + = + =
= + (i-esima rec)
2 2
( ) 2 ( )2
log (1) log
ii
nf n in f
n n nf n n n
= + =
= + = + 2( ) ( log )f n n n⇒ ∈Ω
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
QUICKSORTResolución recurrencia peor caso
( ) ( 1) (1ª rec)
( 1) ( 2) (2ª rec)
( 1) ( 2) ( 3) (3ª )
f n n f n
n n f n
f
= + − =
= + − + − =
63
La recursión termina cuando (n-i)=1Por tanto, habrá i=n-1 llamadas recursivas
1
0
( 1) ( 2) ( 3) ... (3ª rec)
( ) ( ) (i-esima rec)i
j
n n n f n
n j f n i−
=
= + − + − + − =
= − + −∑
1 2
0 0
2 2
0 0
( ) ( ) ( ) ( ) (1)
( 2)( 1)( ) ( ) (1) ( 1) 12
i n
j j
n n
j j
f n n j f n i n j f
n nn j f n n
− −
= =
− −
= =
= − + − = − +
− −= − + = − − +
∑ ∑
∑ ∑2( ) ( )f n n⇒ ∈Ο
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
Coste QUICKSORT
8
4 4
8
7 1
6 1
64
2 2 2 2
1 1 1 1 1 1 1 1
5 1
4 1
3 1
2 1
1 1
Caso mejor
Ω(n lg2n)
Caso peor
Ο(n2)
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS
QUICKSORT mediana (el pivote es la mediana)
En la versión anterior se cumple que el caso mejor es cuando el elemento seleccionado es la mediana.En este algoritmo estamos forzando el caso mejor.Obtener la mediana
65
Obtener la medianaCoste menor que Ο(nlgn)Se aprovecha el recorrido para reorganizar elementos y para encontrar la mediana en la siguiente subllamada.Su complejidad es por tanto de Θ(nlgn).
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS: EJERCICIOS
función DESPERDICIO (n:natural)
para i=1 hasta n hacerpara j=1 hasta i hacer
ESCRIBIR i,j,n ;fpara ESCRIBIR ∈ Θ(1)
66
fparafparasi n>0 entonces
para i=1 hasta 4 hacerDESPERDICIO(n/2);
fparafsi
fin
ESCRIBIR ∈ Θ(1)
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS: EJERCICIOS
función EJEMPLO (n, a:entero):entero;var r:entero fvar;
si a2 > n entonces devuelve 0;si_no
r EJEMPLO(n 2a);
67
r=EJEMPLO(n,2a);opción
n<(r+a)2 devuelve r;n≥(r+a)2 devuelve r+a;
fopciónfsi
fin
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS: EJERCICIOS
funcion ORD(n: N ; v:vector[N]);si (n>0) entonces
ORD(n div 2,v);QuickSortMediana(v,1,n);
fsi;fin
68
fin
4. Calculo de ComplejidadesALGORITMOS RECURSIVOS: EJERCICIOS
función PAL (A:vector[N]; iz,de:N):boolvar n,i:N;n=de-iz+1;opcion
(n <=1): devuelve (CIERTO) ;(n > 1): para i 1 hasta n hacer
69
(n > 1): para i=1 hasta n hacerImprimir("A")
fpara;si (A[iz]=A[de]) entonces
devuelve(PAL(A,iz+1,de-1));sino
devuelve(FALSO) ;finsi;
fopcionfin
5. AnexoEXPRESIONES FRECUENTES
0
2
1
2 3
1. (1),
2. ( 1) ( )2
1
n
i
n
c c
ni n n
n
≥
=
∈Θ ∀ ∈
= + ∈Θ∑
∑
1
1
17. (lg )
18. (1) si 1
n
i
n
ii
ni
rr
=
∈Θ
∈Θ >
∑
∑
70
2 3
1
1
1
1
1
1
0
13. ( 1)( ) ( )3 2
4. ( ),
5. ( ) ( ),
16. ( ), 11
i
nk k
i
nk k
i
nni n
i
ni n n n
i n k
n i n k
rr r rr
=
+
=
+
=
+
=
= + + ∈Θ
∈Θ ∀ ∈
− ∈Θ ∀ ∈
−= ∈Θ ≠
−
∑
∑
∑
∑
1
1
1
1
0
9. lg ( lg )
10. 2 2 2 1 ( 2 )
11. 2 (1)
i
n
i
ni n n n
i
ni
i
r
i n n
i n n
i
=
=
−
=
−
=
∈Θ
= − + ∈Θ
∈Θ
∑
∑
∑
5. AnexoEXPRESIONES FRECUENTES
1
1
12. ( ), 1
13. (1), 1
ni n
i
ni
ir nr r
ir r
−
=
−
∈Θ ∀ >
∈Θ ∀ >
∑
∑
71
1
1
1
114. (1)!
15. 2 (2 )
16. ! ( )
i
n
i
nn n
i
n
i
ni
nn ne
=
=
=
∈Θ
⎛ ⎞ = ∈Θ⎜ ⎟⎝ ⎠
⎛ ⎞∈Θ ⎜ ⎟⎝ ⎠
∑
∑
0·2
nn
a aS n +=
progresión aritmética
5. AnexoSUMA DE SERIES
0
Donde:
Primer elemento de la serie
n-esimo elemento de la serie
Suma de los n primeros elementos de la serie
n
n
a
a
S
=
=
=
72
0
0
1· 11
1,1
n
n
n
rS a rr
aS r nr
−= >
−
= < →∞−
progresión geométrica Razon de la serie geometrica r =
2
2 3 1
2 3 1
1 2
1 2 ( 1)
nn
n nn
n n
S r r nr
rS r r n r nr
S rS r r r r nr
+
+
= + + +
= + + − +
− = + + + −
progresión aritmético-geométrica
5. AnexoSUMA DE SERIES
73
2 3 1
2 3 1 1 11
(1 )
·1 1 1 1
n n
n nn
ni
n n n ni
n
S rS r r r r nr
r S r r r r nr
rr r r r nr nr n rS
r r r r
+
+ + +=
+ + +
− = + + + −
+ + + −= − = −
− − − −
∑
5. AnexoRECURRENCIAS FRECUENTES
REDUCCIÓN DEL PROBLEMA POR RESTAS (c>0)
0
0 /
1 (1)'
( ) Solución: 1 ( )· ( )
1 ( )n c
ab n n
f n a na f n c b n n
a a
< →Θ≤⎧
= →Θ⎨ − + >⎩ > →Θ
74
0 2
0 /
1 ( )'
( ) Solución: 1 ( )· ( ) ·
1 ( )n c
a nb n n
f n a na f n c b n n n
a a
< →Θ≤⎧
= →Θ⎨ − + >⎩ > →Θ
0 1
0 /
1 ( )'
( ) Solución: 1 ( )· ( ) ·
1 ( )
k
kk
n c
a nb n n
f n a na f n c b n n n
a a
+
< →Θ≤⎧
= →Θ⎨ − + >⎩ > →Θ
5. AnexoRECURRENCIAS FRECUENTES
REDUCCIÓN DEL PROBLEMA POR DIVISIONES (c>1)
0
0 lg
1 (1)'
( ) Solución: 1 (lg )· ( / )
1 ( )a
ab n n
f n a na f n c b n n
a n
< →Θ≤⎧
= →Θ⎨ + >⎩ > →Θ
75
0
0 lg
1 ( )'
( ) Solución: 1 ( lg )· ( / )
1 ( )a
a nb n n
f n a n na f n c bn n n
a n
< →Θ≤⎧
= →Θ⎨ + >⎩ > →Θ
0
0 lg
( )'
( ) Solución: ( lg )· ( / ) ·
( )
k k
k kk
k a
a c nb n n
f n a c n na f n c b n n n
a c n
< →Θ≤⎧
= →Θ⎨ + >⎩ > →Θ
5. AnexoALGORITMOS DE ORDENACION
DirectosInserción directaInserción binariaSelección directaIntercambio directo (burbuja)
76
AvanzadosMergesort QuicksortHeapsortShell
5. AnexoALGORITMOS DE ORDENACION
INSERCIÓN DIRECTA
función INSERCION_DIRECTA (var a:vector[natural]; n: natural)var i,j: entero; x:natural fvar
para i=2 hasta n hacerx=a[i]; j=i-1;
77
mientras (j>0) ∧ (a[j]>x) hacera[j+1]=a[j];j=j-1;
fmientrasa[j+1]=x;
fparafin
5. AnexoALGORITMOS DE ORDENACION
INSERCIÓN BINARIA
función INSERCION_BINARIA (var a:vector[natural]; n: natural)var i, j, iz, de, m: entero; x:natural fvar
para i=2 hasta n hacerx=a[i]; iz=1; de=i-1;
78
mientras (iz≤de) hacerm= (iz+de)/2;si a[m]>x entonces de= m-1
si_no iz=m+1fsi
fmientraspara j=i-1 hasta iz hacer (*decreciente*)
a[j+1]=a[j];fparaa[iz]=x;
fparafin
5. AnexoALGORITMOS DE ORDENACION
SELECCIÓN DIRECTA
función SELECCION_DIRECTA (var a:vector[natural]; n:natural)var i, j, posmin: entero; min:natural fvar
para i=1 hasta n-1 hacermin=a[i]; posmin=i;
79
para j=i+1 hasta n hacersi a[j]<min entonces
min=a[j]; posmin=j;fsi
fparaa[posmin]=a[i]; a[i]=min;
fparafin
5. AnexoALGORITMOS DE ORDENACION
INTERCAMBIO DIRECTO (Burbuja)
función INTERCAMBIO_DIRECTO (var a:vector[natural]; n:natural )var i,j:entero fvar
para i=2 hasta n hacerpara j=n hasta i hacer
80
si a[j]<a[j-1] entoncesSWAP(a[j],a[j-1]);
fsifpara
fparafin
5. AnexoALGORITMOS DE ORDENACION
QUICKSORT central
función QUICKSORT_SIN_CENTINELA (var a:vector; pi,pf:indice)var i,j: indice; x: elemento fvarcomienzo
si pi<pf entoncesx=a[(pi+pf)/2]; i=pi; j=pf;
81
repetirmientras a[i]<x hacer i=i+1 fmientrasmientras a[j]>x hacer j=j-1 fmientrassi i≤j entonces
SWAP(a[i],a[j]); i=i+1; j=j-1;fsi
hasta i>j;QUICKSORT_SIN_CENTINELA (a,pi,j);QUICKSORT_SIN_CENTINELA (a,i,pf);
fsifin