708
Capítulo 16 Búsqueda y ordenamiento
16.4 Invariantes
Después de escribir una aplicación, un programador comúnmente la prueba a conciencia. Es bastante difícil
crear un conjunto exhaustivo de pruebas, y siempre es posible que un caso específi co no se evalúe. Una técnica
que nos puede ayudar a probar nuestros programas en forma exhaustiva es el uso de las invariantes. Una
invarian-
te
es una aserción (vea la sección 13.13) que es verdadera antes y después de ejecutar una sección del código. Las
invariantes son matemáticas por naturaleza, y sus conceptos son más aplicables en el lado teórico de las ciencias
computacionales.
El tipo más común de invariante es una
invariante de ciclo
, la cual es una aserción que permanece siendo
verdadera
antes de la ejecución del ciclo,
después de cada iteración del cuerpo del ciclo, y
cuando termina el ciclo.
Una invariante de ciclo escrita en forma apropiada nos puede ayudar a codifi car un ciclo de manera correcta.
Hay cuatro pasos para desarrollar un ciclo a partir de una invariante de ciclo.
1.
Establecer los valores iniciales para las variables de control de ciclo.
2.
Determinar la condición que hace que el ciclo termine.
3.
Modifi car la(s) variable(s) de control, de manera que el ciclo progrese hacia su terminación.
4.
Comprobar que la invariante siga siendo verdadera al fi nal de cada iteración.
•
•
•
n =
O(log n)
O(n)
O(n log n)
O(n
2
)
1
2
3
4
5
10
100
1000
1,000,000
1,000,000,000
0
1
1
1
1
1
2
3
6
9
1
2
3
4
5
10
100
1000
1,000,000
1,000,000,000
0
2
3
4
5
10
200
3000
6,000,000
9,000,000,000
1
4
9
6
25
100
10,000
10
6
10
12
10
18
Figura 16.13
| Número de comparaciones para las notaciones comunes de Big O.
Algoritmo
Ubicación
Big O
Algoritmos de ordenamiento:
Ordenamiento por selección
Ordenamiento por inserción
Ordenamiento por combinación
Ordenamiento de burbuja
Sección 16.3.1
Sección 16.3.2
Ejercicio 16.3.3
Ejercicios 16.3 y 16.4
O(n
2
)
O(n
2
)
O(nlogn)
O(n
2
)
Figura 16.12
| Algoritmos de búsqueda y ordenamiento con valores de Big O.
(Parte 2 de 2).
16_MAQ_CAP_16_DEITEL.indd708
4/19/081:29:39AM