Complejidad P3

[vjuri23]

Holaa, en la pregunta 3 se pide una complejidad O(MK), siendo M el largo de cada subárbol buscado y K el número de consultas. Esto me parece extraño, porque 1) M es variable, entonces para la complejidad ¿elijo el M más grande? ¿O debe revisarse consulta por consulta? 2) En algún momento va a ser necesario recorrer el árbol completo ¿No? Como la cantidad de nodos de este árbol es N, va a haber al menos 1 operación escrita en términos de O(n), entonces, ¿Cómo puedo revisar que esto esté dentro del margen de complejidad O(MK)? Considerando que solo sé que M <= N. En esencia (creo que ya lo habían preguntado igual, pero no hay respuesta todavía), ¿La complejidad no depende de N más que de M? ¿Cómo puedo pasar de N a M? Gracias de antemano.

[benjavicente]

1. M es variable, entonces para la complejidad ¿elijo el M más grande? ¿O debe revisarse consulta por consulta?

Eso quiere decir que el tiempo de búsqueda tiene complejidad $O(M)$ en cada una de las $K$ búsquedas (si entendí bien, lo último)

2. En algún momento va a ser necesario recorrer el árbol completo ¿No? Como la cantidad de nodos de este árbol es N, va a haber al menos 1 operación escrita en términos de O(n) ...

Sí, aunque la complejidad que nos enfocamos es la búsqueda. Todo el programa debería ser $O(N \log(N) + M \times K)$ si utilizan una de las estrategias de iteración del árbol principal, dadas en el anexo y la cápsula.

..., ¿Cómo puedo revisar que esto esté dentro del margen de complejidad O(MK)? Considerando que solo sé que M <= N. En esencia (creo que ya lo habían preguntado igual, pero no hay respuesta todavía), ¿La complejidad no depende de N más que de M? ¿Cómo puedo pasar de N a M? Gracias de antemano.

La idea es enfocarse en la búsqueda al final. Los tests de la parte 3 tratan de enfocarse más en $O(M \times K)$ que $O(N \log(N))$, aunque una complejidad de armar el índice de búsqueda mayor a $O(N \log(N))$ podría perjudicar mucho el tiempo.

[vjuri23]

Pero, mi duda es, si quiero que cada búsqueda sea O(M) y quiero usar una tabla de hash, ¿Cómo garantizo esa complejidad? Porque la distribución que se consiga en la tabla de hash va a depender del input en particular, vale decir, yo no puedo garantizar que cada hash tenga O(M) registros, porque la función de hash trabaja sobre el espacio completo, no sobre mi input particular (vale decir, mapea el espacio completo de manera más o menos equitativa, no mi input). Así, si tengo mala suerte y todos los registros quedan con el mismo hash voy a tener una complejidad de O(cantidad de subárboles) que no es necesariamente O(M).

En esencia, ¿hay que usar estrategias adicionales a la tabla de hash para garantizar la búsqueda O(M)? Y de ser así ¿Cómo lo hago? (Porque nuevamente, la cantidad de subárboles no depende solo de M, si no también de N). Así, tengo entendido que hashear los registros de forma eficiente no me garantiza que en cada celda van a haber O(M) subárboles (especialmente si M es pequeño), por lo que, con una búsqueda estándar la complejidad no sería O(M). En una de esas tengo algún error conceptual, porque, por más que lo pienso, no es posible conseguir complejidad O(M) para cada consulta.

[benjavicente]

Así, si tengo mala suerte y todos los registros quedan con el mismo hash voy a tener una complejidad de O(cantidad de subárboles) que no es necesariamente O(M).

Se asume que la tabla de hash es suficientemente grande para que las colisiones sean despreciables (no es necesario un número taaan grande para acercarse a eso). Un hash perfecto (difícil en la práctica) lega a ese $O(M)$ sin nada más. Nota que también se ignora iterar por todas las posiciones. Entonces, la complejidad aún más "real" que esperamos es más como

$$O(N\log(N) + K \times (M + R + S))$$

Porque se tienen que mostrar los $R$ resultados y se tienen que saltar las $S$ colisiones que hay en una tabla de hash de tamaño $T$. El $O(S)$ usualmente es mucho menor que $O(N\log(N)/T)$ (cantidad de elementos promedio en cada índice del hash table, que por lo que entendí, es el factor que comentas), dado que se repiten muchas veces el mismo árbol, lo que entraría a $R$, que hay que imprimir.

---

Resumiendo, al final la complejidad no es $O(M)$ perfecto por cada búsqueda, pero es lo importante que queremos que se enfoquen en esta parte 😅