patterns - java data structures and algorithms

¿Comparación de estos dos algoritmos?

Question

Así que me presentan un problema que dice. "Determine si una cadena contiene todos los caracteres únicos"

Así que escribí esta solución que agrega cada carácter a un conjunto, pero si el carácter ya existe devuelve falso.

private static boolean allUniqueCharacters(String s) {

    Set<Character> charSet = new HashSet<Character>();
    for (int i = 0; i < s.length(); i++) {
        char currentChar = s.charAt(i);
        if (!charSet.contains(currentChar)) {
            charSet.add(currentChar);

        } else {
            return false;
        }

    }
    return true;

}

Según el libro que estoy leyendo esta es la "solución óptima".

public static boolean isUniqueChars2(String str) {
    if (str.length() > 128)
        return false;

    boolean[] char_set = new boolean[128];

    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);

        if (char_set[val]) {
            return false;
        }
        char_set[val] = true;
    }

    return true;
}

Mi pregunta es, ¿mi implementación es más lenta que la presentada? Supongo que sí, pero si una búsqueda Hash es O (1), ¿no tendrían la misma complejidad?

Gracias.

Answer 1

Ambos algoritmos tienen una complejidad de tiempo de O (N). La diferencia está en su complejidad espacial .

La solución del libro siempre requerirá un almacenamiento de 128 caracteres: O(1) , mientras que los requisitos de espacio de su solución variarán linealmente de acuerdo con la entrada: O(N) .

El requisito de espacio del libro se basa en un conjunto de caracteres supuestos con 128 caracteres. Pero esto puede ser bastante problemático (y no escalable) dada la probabilidad de necesitar diferentes conjuntos de caracteres.

Answer 2

Como dijo Amadan en los comentarios, las dos soluciones tienen la misma complejidad de tiempo O (n) porque tiene un bucle for en la cadena y realiza operaciones de tiempo constante en el bucle for. Esto significa que el tiempo que lleva ejecutar sus métodos aumenta linealmente con la longitud de la cadena.

Tenga en cuenta que la complejidad del tiempo se trata de cómo cambia el tiempo que toma cuando cambia el tamaño de la entrada. No se trata de qué tan rápido es con datos del mismo tamaño.

Para la misma cadena, la solución "óptima" debería ser más rápida porque los conjuntos tienen algunas sobrecargas sobre los arreglos. El manejo de matrices es más rápido que el manejo de conjuntos. Sin embargo, para que la solución "óptima" funcione, necesitaría una serie de longitud 2 ^ 16. Esa es la cantidad de valores char diferentes que hay. También deberías eliminar la comprobación de una cadena más larga que 128.

Este es uno de los muchos ejemplos de la compensación entre el espacio y el tiempo. Si quieres que vaya más rápido, necesitas más espacio. Si quieres ahorrar espacio, tienes que ir más lento.

Answer 3

El cuello de botella de su implementación es que un conjunto tiene una complejidad de búsqueda (e inserción) * de O(log k) , mientras que la matriz tiene una complejidad de búsqueda en O(1) .

Esto suena como que tu algoritmo debe ser mucho peor. Pero, de hecho, no lo es, ya que k está limitado por 128 (de lo contrario, la implementación de referencia sería incorrecta y produciría un error fuera de los límites) y se puede tratar como una constante. Esto hace que el conjunto de búsqueda O(1) también tenga constantes un poco más grandes que la búsqueda de matriz.

* Asumiendo una implementación sana como árbol o hashmap. La complejidad del tiempo del mapa de hash en general no es constante, ya que rellenarlo necesita un log(n) operaciones de cambio de tamaño para evitar el aumento de las colisiones que conducirían a un tiempo de búsqueda lineal, consulte, por ejemplo, here y here para obtener respuestas sobre el flujo de apilamiento.

Este artículo incluso explica que Java 8 por sí mismo convierte un hashmap en un árbol binario ( O(n log n) para la conversión, O(log n) para la búsqueda) antes de que su tiempo de búsqueda degenere a O(n) debido a demasiados colisiones

Answer 4

El hashmap es en teoría aceptable, pero es un desperdicio.

Un hashmap se construye sobre una matriz (por lo que es ciertamente más costoso que una matriz), y la resolución de colisiones requiere espacio adicional (al menos el doble del número de elementos). Además, cualquier acceso requiere el cálculo del hash y, posiblemente, la resolución de colisiones.

Esto agrega una gran cantidad de gastos generales en términos de espacio y tiempo, en comparación con una matriz recta.

También tenga en cuenta que es una especie de folklore que una tabla hash tenga un comportamiento O (1). El peor de los casos es mucho peor, los accesos pueden tardar hasta O (N) en una tabla de tamaño N.

Como observación final, la complejidad del tiempo de este algoritmo es O (1) porque usted concluye falso en el peor cuando N> 128.

Answer 5

Su algoritmo también es O(1) . Puede pensar en la complejidad, como la how my algorithm will react to the change in amount of elements processed . Por lo tanto, O(n) y O(2n) son efectivamente iguales.

La gente está hablando de la notación O como tasa de crecimiento here

Answer 6

Su solución podría ser más lenta que la solución del libro. En primer lugar, una búsqueda de hash tiene idealmente una búsqueda de tiempo constante. Pero, la recuperación del objeto no será si hay múltiples colisiones de hash. En segundo lugar, incluso si se trata de una búsqueda de tiempo constante, generalmente hay una sobrecarga significativa en la ejecución de la función de código hash en comparación con la búsqueda de un elemento en una matriz por índice. Es por eso que es posible que desee ir con la búsqueda de matriz. Sin embargo, si comienza a tratar con caracteres Unicode que no son ASCII, es posible que no desee utilizar el enfoque de matriz debido a la gran cantidad de sobrecarga de espacio.