Ciclo invariante

De manera informal, ciclo invariante es algún predicado o condición que se mantiene en cada iteración de un ciclo. Por ejemplo:

int j = 9; for(int i=0; i<10; i++) j--; 

En este ejemplo se cumple la invariante de ciclo para cada iteración, ya que se mantiene la condición siguiente:

 i + j == 9 

Otra invariante más débil es:

i >= 0 && i < 10 //(condición terminal)  //o bien  j <= 9 && j >= 0 

Las invariantes de ciclo sirven para probar que un algoritmo esté correcto.

Propiedades

• Inicialización. Es verdadera desde la primera iteración.

• Mantenimiento. Es verdadera después de una iteración del ciclo. Se mantiene verdadera antes de la iteración próxima.

• Terminación. Cuando finaliza el ciclo, la invariante aporta una propiedad que indica que el algoritmo es correcto.

Ejemplos

Insertion sort

import java.util.Arrays; class InsertionSort{ public static void main(String[]args){ int[]array={5,2,4,6,1,3}; String out=""; out+=Arrays.toString(array)+"\nResult:\n"; //start for(int i=1;i<array.length;i++){ int key=array[i]; int j=i-1; out+="array["+j+"] > key = "+array[j] +" > "+key+" = "+(array[j]>key)+"\n"; while(j>=0 && array[j]>key ){ array[j+1]=array[j];out+=" \tarray["+j+"+1]=array["+j+"]\n"; j--; } array[j+1]=key; } out+=Arrays.toString(array)+"\n"; System.out.println(out); } } 

Referencias

Introduction to Algorithms. Third Edition. Thomas H. Cormen. 2009.

•   Datos: Q2238838