Lo demuestras usando loop invariant. Entonces, ¿qué es un bucle invariante? Es una declaración que es verdadera antes de la primera iteración, y se conserva a lo largo de las iteraciones del ciclo (es decir, es verdadera antes de [math] i [/ math] -th iteration, y sigue siendo verdadera después de completar [math] i [/ math] -th iteración).
El verdadero problema al probar la corrección de los algoritmos es encontrar qué afirmación hace que un buen bucle sea invariable.
Para la búsqueda lineal, eso sería lo siguiente:
“Al comienzo de la iteración [matemática] i [/ matemática], la submatriz [matemática] A [1 … (i-1)] [/ matemática] no contiene la clave [matemática] v [/ matemática]”
- Cómo demostrar que O (f (n) - g (n)) no es necesariamente igual a O (f (n)) - O (g (n))
- ¿Qué significa: = significa en algoritmos?
- ¿Cuál es el algoritmo de programación monotónico de velocidad en los sistemas operativos?
- ¿Cuál es el mejor enfoque para resolver el problema que CRYPTO preguntó en el concurso de codificación PRAVEGA 2014 celebrado en Codechef el 9 de noviembre?
- ¿Cuál será el algoritmo de rotación correcto en C?
Probemos esto:
- inicialización: antes del inicio de la primera iteración, la submatriz [matemática] A [1… 0] [/ matemática] está vacía (trivialy), y la matriz vacía seguramente no contiene [matemática] v [/ matemática].
- mantenimiento: Supongamos que antes de [math] i [/ math] -th iteration, subarray [math] A [1… (i-1)] [/ math] no contiene [math] v [/ math]. En la iteración [matemática] i [/ matemática], verificamos si [matemática] A [i] = v [/ matemática]. Si eso es cierto, sacamos el índice [math] i [/ math] y dejamos de buscar. Si eso no es cierto, entonces sabemos [matemáticas] A [i] \ ne v [/ matemáticas] y por suposición, [matemáticas] A [j] \ ne v [/ matemáticas] donde [matemáticas] j = 1,2, …, i-1 [/ math] así que cuando combinamos esas dos afirmaciones, [math] A [j] \ ne v [/ math] donde [math] i = 1, 2, 3, …, i [/ math] . Finalmente, al final de la iteración del ciclo, cuando aumentamos [math] i = i + 1 [/ math], invariante seguirá siendo verdadero.
- terminación: el bucle puede terminar en dos casos. El primero es cuando encontramos el elemento [math] v [/ math], en cuyo caso terminamos y devolvemos el índice en el que encontramos la clave [math] v [/ math]. En otro caso, el ciclo terminará después de la iteración a través de todos los elementos [math] n [/ math]. Cuando eso suceda, el índice será [matemático] i = n + 1 [/ matemático], y por el subconjunto invariante [matemático] A [1… n] [/ matemático] no contiene [matemático] v [/ matemático ] entonces volvemos NIL.
