¿Por qué mi código está dando “Límite de tiempo excedido”?
Hoy mientras resolvía una pregunta en Leetcode, apliqué DFS en un grafo dirigido que se ejecuta en tiempo O(N), pero mi código estaba dando TLE, así que después de intentarlo muchas veces, revisé los comentarios y encontré un código aceptado que también se ejecuta en O(N). Ahora estoy confundido de por qué mi código no está siendo aceptado y está dando límite de tiempo excedido.
Mi código:
public:
int ans=INT_MIN;
vector<><int>> gr;
void dfs(int head, int time, vector<int> inform){
if(gr[head].size()==0) {ans=max(ans,time);return;}
for(auto next:gr[head]){
dfs(next, inform[head]+time, inform);
}
}
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
gr.resize(n);
for(int i=0 ; i<n ;="" i++){="" if(manager[i]!="-1)" gr[manager[i]].push_back(i);="" }="" dfs(headid,0,="" informtime);="" return="" ans;="" }="" ```="" uno="" de="" los="" códigos="" aceptados:="" ```="" int="" numofminutes(int="" n,="" int="" headid,=""></n><int>& manager, vector<int>& informTime) {
int res = 0;
for (int i = 0; i < n; ++i)
res = max(res, dfs(i, manager, informTime));
return res;
}
int dfs(int i, vector<int>& manager, vector<int>& informTime) {
if (manager[i] != -1) {
informTime[i] += dfs(manager[i], manager, informTime);
manager[i] = -1;
}
return informTime[i];
}
Si alguien necesita el enlace de la pregunta:
https://leetcode.com/problems/time-needed-to-inform-all-employees/
davy.ai
Como experto en TI especializado en c++, estructuras de datos, gráficos, estilo de codificación y búsqueda en profundidad, es esencial analizar la situación y comprender la razón de la diferencia de rendimiento entre los dos códigos.
En el problema dado, ambos códigos mencionados utilizan DFS en un gráfico dirigido con una complejidad temporal de O(N). Sin embargo, el primer código, después de varios intentos de optimización, aún falló con un error de límite de tiempo excedido (TLE), mientras que el segundo código fue aceptado.
Al comparar los dos códigos, se observa que el segundo código es más simple y eficiente en estructura. Los parámetros de entrada pasados a la función numOfMinutes son manipulados dentro de la función dfs, y el valor manager[i] se establece en -1 si se encuentra, y la recursión continúa hacia el padre del nodo actual hasta que se encuentra -1.
El primer código compara el tamaño del vector gr[head] en cada iteración de dfs, lo que aumenta el tiempo de computación. Por lo tanto, en lugar de ejecutar dfs de forma recursiva, se itera cada elemento de gr[head] en un ciclo, lo que aumenta aún más el tiempo de ejecución.
Por lo tanto, una razón para la diferencia de rendimiento entre los dos códigos puede atribuirse a la variación en el tiempo de ejecución causada por el ciclo utilizado en el primer código y al enfoque recursivo optimizado aplicado en el segundo código.