Número promedio de intervalos de una entrada en 0..N

Question

La pregunta surgió cuando se examinó "Encontrar los números que faltan K en este conjunto que supuestamente cubriría [0..N]".

El autor de la pregunta solicitó respuestas de CS en lugar de respuestas basadas en ecuaciones, y su propuesta fue ordenar la entrada y luego iterar sobre ella para enumerar los K números que faltan.

Si bien esto me parece bien, también parece un desperdicio. Tomemos un ejemplo:

• N = 200
• K = 2 (consideraremos K < < N)
• elementos que faltan: 53, 75

El "ordenados" conjunto puede se representará como: [0, 52] U [54, 74] U [76, 200], que es mucho más compacto que la enumeración de todos los valores del conjunto (y permite recuperar los números que faltan en operaciones O (K), que se compararán con O (N) si el conjunto está ordenado).

Sin embargo, este es el resultado final, pero durante la construcción de la lista de intervalos podría ser mucho mayor, ya que vamos a alimentar el uno elementos a la vez ....

Veamos, por lo tanto, introducimos otra variable: Deje I ser la cantidad de elementos del conjunto que alimentamos a la estructura hasta el momento. Entonces, podemos tener en el peor: min((N-K)/2, I) intervalos (creo ...)

De lo cual deducimos que el número de intervalos alcanzados durante la construcción es el máximo encontrado para I en [0..N], el peor caso siendo (N-K)/2 así O(N).

Tengo sin embargo el presentimiento de que si la entrada es al azar, en lugar de estar especialmente diseñado, que podría recibir una cantidad límite inferior ... y por lo tanto la pregunta siempre es tan complicado:

¿Cuánto intervalos. .. en promedio ?

Answer 1

Su enfoque frente al propuesto con la clasificación parece ser una solución clásica, cuyas operaciones son baratas y cuál es costosa.

Encuentro su notación un poco confuso, así que por favor me permite utilizar mi propia:

Vamos S ser el conjunto. Deje n el número de elementos en el conjunto: n = |S|. Deje max ser el número más grande en el conjunto: max = max(S). Deje k ser la cantidad de elementos que no están en el conjunto: k = |{0,...,max} \ S|.

Para la solución de clasificación, podríamos insertar muy económicamente todos los elementos n en S usando hash. Eso llevaría O(n) esperado. Luego, para encontrar los k elementos faltantes, ordenamos el conjunto en O(nlogn) y luego determinamos los elementos faltantes en O(n).

Es decir, el costo total para agregar n elementos y luego encontrar los elementos faltantes k lleva O(n) + O(nlogn) + O(n) = O(nlogn) esperado.

---

usted sugiere un enfoque diferente en el que se representa el conjunto como una lista de subconjuntos densos de S. ¿Cómo implementaría tal estructura de datos? Sugiero un árbol ordenado (en lugar de una lista) para que una inserción sea eficiente. Porque, ¿qué tienes que hacer para insertar un nuevo elemento e? Yo creo que hay que:

1. Encuentra el potencial subconjunto (s) candidato en el árbol donde e podría añadirse
2. Si un subconjunto ya contiene e, nada tiene que hacer.
3. Si un subconjunto contiene e+1 y otro subconjunto contiene e-1, fusionar los subconjuntos juntos y añadir e al resultado
4. Si un subconjunto ya contiene e+1, pero e-1 no está contenida en S, añadir e a ese subconjunto
5. Si un subconjunto ya contiene e-1, pero e+1 no está contenida en S, añadir e a ese subconjunto
6. de lo contrario, crear un nuevo subconjunto sujetándolo sólo por el elemento de inserción y e en el árbol.

Podemos esperar que encontrar los subconjuntos necesarios para las operaciones anteriores tome O(logn). Las operaciones de 4. o 5. toman un tiempo constante si representamos los subconjuntos como pares de enteros (solo tenemos que disminuir el límite inferior o incrementar el límite superior). 3. y 6. potencialmente requieren cambiar la estructura del árbol, pero esperamos que tome como máximo O(logn), por lo que toda la "inserción" no tomará más que O(logn).

Ahora con una estructura de datos en su lugar, podemos determinar fácilmente los números que faltan k al recorrer el árbol en orden y recoger los números que no están en ninguno de los subconjuntos. Los costos son lineales en el número de nodos en el árbol, que es <= n/2, por lo que los costos totales son O(n) para eso.

Sin embargo, si tenemos en cuenta de nuevo las operaciones secuencia completa, obtenemos para n insertos O(nlogn) + O(n) para encontrar los k números que faltan, por lo que los costes totales son de nuevo O(nlogn).

Esto no es mejor que los costos esperados del primer algoritmo.

---

Una tercera solución es el uso de un valor booleano array para representar el conjunto y un solo número entero max para el elemento más grande en el conjunto.

Si se agrega un elemento e al conjunto, establezca array[e] = true. Puede implementar el tamaño variable del conjunto usando table expansion, por lo que los costos de insertar un elemento en el conjunto son constantes.

Para recuperar los elementos que faltan, solo recoge esos elementos f donde array[f] == false. Esto llevará O(max).

El costo total para insertar n elementos y encontrar los k faltantes es por lo tanto: O(n) + O(max). Sin embargo, max = n + k, y así obtenemos como los costos generales O(n + k).

---

Un cuarto método, que es un cruce entre el tercero y el uso de hashing es la siguiente, que también utiliza el hashing, pero no requiere la clasificación.

Almacena tu conjunto S en un conjunto de hash, y también almacena el elemento máximo en S en una variable max. Para encontrar los k que faltan, primero genere un conjunto de resultados R que contenga todos los números {0,...,max}. Luego itere sobre S y borre todos los elementos en S desde R.

Los costos para eso también son O(n + k).