6.3.2. Problema de las n reinas.
Evaluación de la eficiencia. La evaluación es compleja, ya que el tiempo de ejecución en cada nodo no es constante y el número de nodos generado es difícil de predecir.
- El tiempo de ejecución de la función Criterio depende del nivel. Para nivel i, el número de comprobaciones es (i-1). Está en O(i).
- Número de nodos, en el peor caso:
- Nivel 0: 1
- Nivel 1: n/2 0·n/2 Comprobaciones
- Nivel 2: (n/2)(n-1) 1·(n/2)(n-1) “
- ....
- Nivel n: n!/2 (n-1)·n!/2 “
La cota superior está muy alejada del número real de nodos generados.
Ejemplo. Para n = 4. Número de nodos en el peor caso = 33. Número de nodos generados realmente = 9.