algoritmo que determina si existe un entero duplicado con el tiempo de ejecución previsto $O(n)$

Question

Consideremos una entrada de matriz sin ordenar; queremos determinar si existe un entero duplicado; el algoritmo debería tener el tiempo de ejecución esperado $O(n)$ .

Nota: Queremos analizar el tiempo de ejecución previsto contando el número de comparaciones del algoritmo.

Sé que la fuerza bruta requiere $\Theta(n^2)$ complejidad y el mejor de los casos es $\Theta(1)$ .

Sin embargo, para el análisis del tiempo de ejecución previsto, ¿es equivalente al caso medio? ¿Consideramos todas las posibles complejidades del tiempo de ejecución y tomamos la expectativa sobre ellas?

Como el algoritmo se basará en el número de comparaciones que hagamos.

el número total posible de comparaciones que realizaremos sería un conjunto $\{1,2,3,4,...,n-1,n,n+1,...,2n-3, ......\}$ (donde $1,..,n-1$ son varias las comparaciones que podrían hacerse al comparar $A[0]$ a otros, etc.; y $n$ es el tamaño de la matriz); luego se toma la expectativa, pero ¿cómo decido la probabilidad de cada número de comparaciones? Por ejemplo, si el algoritmo termina con una sola comparación, entonces $A[0] == A[1]$ pero no sé cómo determinar esta probabilidad.

Answer 1

Suponiendo que cada uno de los números de entrada se representa como una cadena determinada de símbolos de un alfabeto finito, se puede construir un trie representando los números que has visto hasta ahora, mientras los lees. Eso detectará automáticamente los duplicados por ti, al tiempo que realiza una cantidad constante de trabajo por símbolo de entrada.

Answer 2

El algoritmo depende en gran medida de la naturaleza de la entrada.

Si la entrada consiste en $n$ enteros de algún tamaño acotado, entonces podemos considerar cada entero como un único símbolo de un alfabeto posiblemente bastante grande, pero finito. Sea $k$ símbolos del alfabeto; a continuación $k$ es una constante fija para cualquier entrada, y cualquier entrada de longitud $>k$ contiene un duplicado por el principio de encasillamiento.

Por ejemplo, si la entrada es una matriz de cualquier longitud que contenga $32$ -enteros de bits, entonces $k=2^{32}.$

El algoritmo para este tipo de problema comienza contando hasta $k+1$ enteros en la entrada. Si el recuento alcanza $k+1,$ el algoritmo devuelve "existe un duplicado"; en caso contrario, realiza hasta $k(k-1)$ comparaciones (el método de la fuerza bruta). Así que en el peor de los casos tenemos $k+1$ pasos de recuento y $k(k-1)$ comparaciones; pero como $k$ es una constante fija, el tiempo de ejecución del algoritmo está acotado, y todo el algoritmo se ejecuta en el peor de los casos $O(1)$ tiempo. (La constante de tiempo para ese $O(1)$ tiempo puede ser bastante grande).

Un tipo de entrada más interesante permite que los enteros de entrada sean cadenas de dígitos de cualquier longitud. Ahora tenemos que decir lo que significa tener una entrada de tamaño $n$ una interpretación razonable es que $n$ es la suma de las longitudes de todas las cadenas (o la suma de las longitudes más el número de cadenas, para permitir la demarcación de las cadenas). Entonces la solución de Henning Makholm (utilizando un trie) se ejecuta en $O(n)$ tiempo en el peor de los casos, lo que implica que tiene $O(n)$ tiempo previsto.

Otra interpretación posible es que permitimos que los enteros sean cadenas de longitud arbitraria, pero suponemos que hay alguna distribución de probabilidad que gobierna el valor de cada entero. Es decir, si $m$ es un número entero dado, entonces hay alguna probabilidad $P(m)$ que el siguiente entero de entrada será igual a $m.$

En esa interpretación hay una probabilidad fija $P_0$ que dos enteros seleccionados al azar de la entrada serán iguales. La longitud esperada de un entero (un límite en el tiempo esperado necesario para comparar dos enteros) también es un valor fijo. Si la primera pasada del algoritmo se limita a comparar el primer y el segundo número entero de la entrada, luego el tercero y el cuarto, luego el quinto y el sexto, etc., a medida que la longitud de la entrada aumenta hasta el infinito la probabilidad de encontrar una coincidencia se aproxima a $1$ y el número esperado de comparaciones antes de encontrar la coincidencia (cuando la hay) se aproxima a una constante.

El número esperado de comparaciones cuando comparamos todos pares posibles de enteros de entrada (hasta el primer par coincidente) es un poco más complicado de tratar, ya que no todos los pares se distribuyen independientemente, pero quizá se pueda demostrar que también está acotado como $n$ llega a infinito; si es así, el tiempo de ejecución esperado de todo el algoritmo es $O(1).$

Answer 3

Tabla hash la búsqueda y la inserción suelen considerarse $O(1)$ en la media. Así que si usted comienza con una tabla hash vacía, ir a través de todos los elementos buscar e insertar al mismo tiempo, se encuentra el elemento en la media en el índice $k=(n+1)/2$ suponiendo que sólo hay un duplicado, por lo que necesita $O(n)$ cálculos hash y comparaciones de igualdad (dentro de la tabla hash) o menos.

Si no se utiliza una tabla hash, sino una lista ordinaria, la comprobación de la colisión es $O(m)$ donde m es la longitud de la lista ordinaria, suponiendo que no detectamos una colisión. Tomando de nuevo la media bajo la misma distribución que antes obtenemos $1/6\,n\,(n + 2)$ . Así que necesitaría $O(n^2)$ comparaciones de igualdad (dentro de la lista ordinaria) o menos.

Los distintos códigos de programa tienen un aspecto muy similar (en Java):

Tabla hash:

HashSet res = new HashSet();
for (int i=0; i<A.size(); i++) {
    if (res.contains(A.get(i))     /* O(1) */
      return true;
    res.add(A.get(i));             /* O(1) */
}
return false;

Lista ordinaria:

ArrayList res = new ArrayList();
for (int i=0; i<A.size(); i++) {
    if (res.contains(A.get(i))     /* O(m) */
      return true;
    res.add(A.get(i));             /* O(1) */
}
return false;

Ahora podemos hacer más explícito el modelo de probabilidad que estaba utilizando. Estoy utilizando una variable aleatoria $X$ para el número de iteraciones del bucle for exterior. La variable está en el rango $\{0, .., n\}$ , $0$ significa que se encontró un duplicado en la primera iteración y se devolvió true. $n$ significa que no se encontró ningún duplicado y se devolvió false.

Trabajé con $P[X=i] = 1/(n+1)$ una distribución uniforme. El esfuerzo del programa puede considerarse como el valor esperado $E[Y]$ de otra variable aleatoria $Y = f(X)$ que calcula el esfuerzo para realizar el bucle X veces. Para la tabla hash tenemos $Y = X$ y para la lista ordinaria tenemos $Y = 1/2\,X\,(X+1)$ despreciando la función add() y considerando únicamente la función contains().

Tabla hash: $$E[Y]=E[X]=\sum_{i=0}^n P[X=i] i=\frac{1}{n+1} \frac{1}{2} n (n+1)=\frac{1}{2} n$$ Lista ordinaria: $$E[Y]=E[\frac{1}{2} X (X+1)]=\sum_{i=0}^n P[X=i] \frac{1}{2} i (i+1)=\frac{1}{n+1} \frac{1}{6} n (n + 1) (n + 2) = \frac{1}{6} n (n+2)$$

La distribución elegida puede considerarse un límite superior; las distribuciones más realistas o que también tienen en cuenta la existencia de múltiples duplicados darían más peso a los valores inferiores de $X$ lo que también implica una mayor ponderación de los valores más bajos de $Y = f(X)$ y, por tanto, al final un valor más bajo de $E[Y]$ .