Esto está lejos de ser una prueba formal, pero, detalles … 🙂
El ejemplo más fácil es probablemente la búsqueda binaria. Una función para describir el peor de los casos:
f (n) = 1 + f (n / 2), n> 1
- ¿Cómo funciona Swype?
- Cómo insertar datos de matriz en una base de datos
- ¿La programación lineal admite un algoritmo de tiempo fuertemente polinómico?
- ¿Qué algoritmos de aprendizaje automático son más adecuados para las entradas 1-hot?
- ¿Cuál es el mejor algoritmo para girar a la izquierda en los semáforos?
f (n) = 1, n = 1
para n> 1 el costo es 1 (examinar el elemento del medio), y dado que estamos viendo el peor de los casos, ese no encontrará el elemento, por lo tanto, debemos verificar en la mitad de los datos, ergeo el costo de la búsqueda binaria en el peor de los casos en un conjunto de n / 2 elementos (por lo tanto, + f (n / 2))
si solo tenemos 1 elemento, el costo es 1 (verificamos el elemento único, ya sea correcto o no).
entonces, para f (n) obtenemos: 1 + f (n / 2) = 1 + 1 + f (n / 4) = 1 + 1 + 1 + f (n / 8) +… + f (n / n ) (f (n / n) es, por supuesto, f (1) y no es necesario realizar más comprobaciones.
Por lo tanto, la recursión se realiza hasta 2 ^ k = n, en cuyo punto llegamos a la condición final, lo que da que k = log2 (n), por lo que el costo es
[matemáticas] \ sum_ {x = 1} ^ {k} 1 = k = log_2 n [/ matemáticas]
