Complejidad del tiempo del conjunto en Java

Question

¿Puede alguien decirme la complejidad del tiempo del código siguiente?

a es una matriz de int.

Set<Integer> set = new HashSet<Integer>(); 
for (int i = 0; i < a.length; i++) { 
    if (set.contains(arr[i])) { 
     System.out.println("Hello"); 
    } 
    set.add(arr[i]); 
} 

creo que es O (n), pero no estoy seguro ya que está utilizando Set y esto contiene métodos también. También está llamando al método add de set.

¿Alguien puede confirmar y explicar cuál es la complejidad temporal de todo el código anterior? Además, ¿cuánto espacio tomaría?

Answer 1

creo que es O (n), ya que se recorre la matriz, y contains y add debe ser constante de tiempo porque es un conjunto basado de hash. Si no se basa en hash y requiere iteración en todo el conjunto para realizar búsquedas, el límite superior sería n^2.

enteros son inmutables, por lo que el espacio complejidad serían 2n, que creo que se simplifica a solo n, dado que las constantes no importan.

Si tuviera objetos de la matriz y del set, entonces tendría referencias 2n y n objetos, por lo que se encuentran en 3n, que sigue siendo lineales (una constante) veces las limitaciones de espacio.

EDITAR-- yep "Esta clase ofrece un rendimiento de tiempo constante para las operaciones básicas (agregar, eliminar, contener y tamaño), suponiendo que la función de dispersión dispersa los elementos correctamente entre los depósitos."

ver here.