6.2. Análisis de tiempos de ejecución.
El tiempo de ejecución depende del número de nodos generados y del tiempo requerido para cada nodo.
Por lo general, el tiempo en cada nodo es constante.
Suponiendo que una solución sea de la forma: (x1, x2, ..., xn), en el peor caso se generarán todas las posibles combinaciones para cada xi.
Si el número de posibles valores para cada xi es mi, entonces se generan:
m1·m2 nodos en el nivel 2
m1·m2· ... ·mn nodos en el nivel n
Ejemplo: para el problema de la suma de subconjuntos mi = 2. El número de nodos generados es:
t(n) = 2 + 22 + 23 + ... + 2n = 2n+1 - 2
Ejemplo: calcular todas las permutaciones de (1, 2, ..., n). En el nivel 1 tenemos n posibilidades, en el nivel 2 n-1, ..., en el nivel n una posibilidad.
t(n) = n + n·(n-1) + n·(n-1)·(n-2) + ... + n! ? O(n!)
En general tendremos tiempos con órdenes de complejidad factoriales o exponenciales.