Consideremos una situación en la que vemos las entradas una por una, siendo cada entrada un $n$ -tupla $(a_1,a_2,...,a_n)$ donde cada $a_i\in\{0,1\}$ . Para cada nueva entrada que veamos, tenemos que responder a dos preguntas:
1) ¿Hemos visto esta entrada antes?
2) ¿Es la entrada dominado por alguna entrada que hayamos visto antes? (Una entrada $A=(a_1,\ldots,a_n)$ se dice que dominado por una entrada $B=(b_1,\ldots,b_n)$ si $a_i\leq b_i$ para todos $i$ .)
¿Con qué rapidez podemos responder a estas dos preguntas para cada entrada?
Para la pregunta 1), podemos utilizar una tabla hash. Comprobamos si la entrada ha sido vista antes en $O(1)$ tiempo, y si no, inserta la entrada en la tabla hash en $O(1)$ tiempo.
Para acomodar la pregunta 2), la forma trivial es comparar la nueva entrada con cada una de las entradas anteriores, lo que llevaría $O(k)$ tiempo, donde $k$ es el número de elementos de la tabla hash. Puede ser hasta $O(2^n)$ tiempo. ¿Hay alguna manera de reducir esto a algo polinómico en $n$ ?
0 votos
El hash de la tupla requiere $O(n)$ tiempo ¿verdad? así que el primer caso no puede ser $O(1)$ a menos que $n$ es constante. Además, para la segunda, ¿quieres decir $O(k \times n)$ (comparado con cualquier otro $k$ y cada comparación es $O(n)$ )
0 votos
@Irvan El hash de cada tupla requiere $O(1)$ tiempo. (Recuerde que estamos considerando el tiempo para responder a las preguntas de cada entrada).
0 votos
Pero cada entrada es $(a_1, \cdots, a_n)$ es decir, consiste en $n$ elementos, ¿verdad? Por lo tanto, si $H$ es la función hash, $H(a_1, \cdots, a_n)$ requiere al menos $O(n)$ .
0 votos
@Irvan Puedes pensar en cada entrada como un entero entre $1$ y $2^n$ (es decir, considerar $a_1a_2\ldots a_n$ como la representación en base $2$ .) Entonces sólo hace falta (caso medio) $O(1)$ tiempo para insertarlo en una tabla hash .