Confundido/a con la complejidad de tiempo y espacio.
Escribí un algoritmo de backtracking que resultó en TLE, lo cual fue esperado.
Pero quería hacer el análisis de complejidad de tiempo para él.
Pensé que haríamos llamadas a la función recursiva 2N veces, luego 2N-1 veces, luego 2N-2 veces, y así sucesivamente.
En total hacemos (2N)! llamadas y en cada llamada usamos un bucle for en 2N elementos.
Por lo tanto, la complejidad de tiempo general es de 2N . (2N)!
Pero este código se ejecuta con la entrada = 6, pero TLEs en la entrada = 7.
Establecer la entrada como 5 o 6 en la complejidad de tiempo da números muy grandes que también deberían resultar en TLE, pero no es así.
¿Dónde estoy equivocado en mi análisis de complejidad?
Pregunta: https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
Código:
“`
class Solution {
public:
int MOD = 1e9 + 7;
<pre><code>long backtrack(int N, int ordersPicked, int ordersDelivered,
vector<bool>& picked, vector<bool>& delivered) {
// Hemos recogido y entregado todos los pedidos.
if (ordersDelivered == N) {
return 1;
}
long ans = 0;
for (int i = 0; i < N; ++i) {
// Recoger un pedido que aún no se ha recogido
if (!picked[i]) {
picked[i] = true;
// Contar las formas después de recoger el pedido actual.
ans += backtrack(N, ordersPicked + 1, ordersDelivered, picked, delivered);
ans %= MOD;
// Paso de backtracking.
picked[i] = false;
}
}
for (int i = 0; i < N; ++i) {
// Entregar un pedido que ha sido recogido pero aún no se ha entregado
if (picked[i] && !delivered[i]) {
delivered[i] = true;
// Contar las formas después de entregar el pedido actual.
ans += backtrack(N, ordersPicked, ordersDelivered + 1, picked, delivered);
ans %= MOD;
// Paso de backtracking.
delivered[i] = false;
}
}
return ans;
</code></pre>
}
int countOrders(int n) {
vector<bool> picked(n), delivered(n);
return backtrack(n, 0, 0, picked, delivered);
}
};
“`
davy.ai
La parte incorrecta en el análisis de complejidad temporal es que se asume que en cada paso hay 2N elementos para recorrer. Sin embargo, esto no es cierto ya que a medida que elegimos órdenes, el número de órdenes para elegir disminuye, y lo mismo ocurre con la entrega. Por lo tanto, el número de elementos para recorrer es menor que 2N en cada paso.
Un análisis más preciso sería que en cada paso, tenemos 2N – órdenesElegidas – órdenesEntregadas elementos para elegir. Al multiplicar esto con el número de llamadas (que es (2N)!), obtenemos una complejidad temporal de O((2N)!(2N – órdenesElegidas – órdenesEntregadas)).
En el peor escenario donde elegimos todas las N órdenes y entregamos todas las N órdenes (es decir, órdenesElegidas = órdenesEntregadas = N), la complejidad temporal se vuelve O((2N)!(2N – N – N)) = O((2N)! / N^2), lo cual es consistente con el comportamiento observado del código (TLE en N = 7).