No definió lo que hace getSuccessor (), pero permítame intentar responder suponiendo que devuelve el nodo con la clave más pequeña mayor que la clave del nodo de entrada. Antes de comenzar con la prueba, haré dos suposiciones más: el peor tiempo de ejecución de getSuccessor () es O (h) y el árbol no se cambiará entre llamadas sucesivas del método. Ahora la prueba es simple. Debe llamar una vez al método para obtener el siguiente sucesor y necesita tiempo O (h) para eso (el peor de los casos ocurre cuando el nodo de entrada es la raíz y el siguiente sucesor es una hoja en profundidad h). Una vez que tenga el próximo sucesor, simplemente puede almacenarlo y para cada otra llamada, puede devolverlo en O (1). Como tiene k-1 llamadas restantes, el tiempo de ejecución es O (k). En combinación con lo anterior, tiene que el tiempo total de ejecución es O (h) + O (k) = O (k + h).
ps Esta prueba es en realidad una explicación de cómo hacerlo en el tiempo O (h + k) ya que no puedo adivinar qué hace su función. Si deja de suponer que el árbol no se cambiará, obtendrá el peor tiempo de ejecución un poco diferente.
- ¿Cuál es la mejor práctica para el aprendizaje de algoritmos y programación?
- ¿Dónde debería comenzar si quiero implementar un algoritmo de detección de movimiento en FPGA?
- ¿Dónde puedo encontrar un algoritmo de ordenación que maneje los números dentro de las cadenas correctamente?
- Cómo comenzar a practicar algoritmos para la codificación
- ¿Qué algoritmos puedo usar para predecir la temperatura o dichos parámetros en función de sus datos históricos?
