Algoritmo eficiente para encontrar el primer nombre disponible

Question

Tengo una matriz que contiene nombres de elementos. Quiero dar al usuario la opción de crear elementos sin especificar su nombre, por lo que mi programa tendrá que proporcionar un nombre predeterminado único, como "Artículo 1".

El desafío es que el nombre tiene que ser único, así que tengo que verificar toda la matriz para ese nombre predeterminado, y si hay un elemento con el mismo nombre, tengo que cambiar el nombre para ser "Artículo 2" y etcétera hasta que encuentre un nombre disponible.

La solución obvia será algo así como que:

String name = "Item "; 
for (int i = 0; !isAvailable(name + i) ; i++); 

Mi problema con que el algoritmo es que se ejecuta en O (N^2).

Me pregunto si existe un algoritmo conocido (o nuevo) más eficiente para resolver este caso.

En otras palabras, mi pregunta es esta: ¿Hay algún algoritmo que encuentre que el primer número mayor que cero que NO existe en una matriz dada, y se ejecuta en menos de N^2?

Answer 1

Usted puede hacer ciertamente en O (N), siendo N el número de elementos en el array:

• Uno de "Punto 1", "Artículo 2", ... "Artículo N +1 "debe ser libre, por lo tanto, cree una matriz de banderas N + 1.
• Recorre los elementos, y para cada nombre si es de la forma "Elemento k" con 0 < k < = N + 1, establece esa marca.
• Escanee la matriz de banderas para la primera bandera clara.

El requisito de memoria adicional es N + 1 bits, lo que sin duda supera a cualquier estructura de datos que almacena realmente todos los N nombres.

Answer 2

Sí, la hay.

Primero ordene la matriz. A continuación, ejecute y devuelva el primer elemento cuyo valor no sea igual a su índice (más 1). El género es O (n log n), el paso final es O (n), por lo que todo es O (n log n).

Si coloca todos los elementos en una tabla hash, puede hacerlo en O (n) a cambio de espacio y en O (1) paso adicional en la creación de nuevos elementos. Dado que cada elemento necesita ser visitado, O (n) es claramente óptimo.

Me interesaría ver si hay una forma O (n) de hacer esto, sin usando cualquier estructura de datos "persistente" como la tabla hash. (Y suponiendo enteros ilimitados, de lo contrario, se podría usar un ordenamiento de depósitos como un algoritmo de clasificación O (n)).

Answer 3

¿Por qué no solo realizar un seguimiento del número máximo hasta la fecha, y cuando necesita uno nuevo, incrementarlo?

Answer 4

Inserte todos los nombres existentes en una tabla hash. Repite tu ciclo, pero haz que esté disponible. Comprueba la tabla hash. Suponiendo un hash decente, es O (nh) donde h es el costo de evaluar el hash.

Answer 5

Se podría tratar de hacer lo siguiente:

primera:

• bucle a través de la lista, y obtener todos los elementos numerados, esto es la complejidad N
• para cada elemento numerado, poner el tema en un árbol (en C++: std :: mapa), se trata de registro de la complejidad (N)

Así que ya lo han construido un mapa con los números utilizados, con la complejidad "registro de N x (N)"

A continuación, itere hasta el árbol y tan pronto como vea un "agujero", use el número. El peor caso es la complejidad N.

Entonces en total, la complejidad es N x log (N) + N, o simplificada: N log (N).

Answer 6

Si solo va a haber un usuario accediendo a esta matriz, ¿por qué no usar el número nanoseconds? Esto, por supuesto, supone que el usuario es mucho más lento que una computadora, lo que parece una suposición segura.

De esta manera, tiene un costo de O (1) para determinar un nombre único.

Answer 7

Un enfoque en tiempo logarítmico, suponiendo que nunca deja "huecos" por borrar elementos:

// Inverse binary search for the last one. 
int upperBound = 1; 
while(isInUse(upperBound)) upperBound *= 2; 

// Standard binary search for the end once we have a ballpark. 
int lowerBound = upperBound/2; 
while(lowerBound < upperBound - 1) 
{ 
    int midpoint = (lowerBound + upperBound)/2; 
    if (isInUse(midpoint)) 
     lowerBound = midpoint; 
    else 
     upperBound = midpoint; 
} 
return upperBound; 

Si los números de artículos pueden ser liberados mediante la supresión, nada menos que la búsqueda lineal funcionará a menos que también mantiene una "lista libre" y elige de eso.