Jaka jest złożoność tego kodu manipulacji ciągami?

Question

Ten fragment kodu pochodzi z książki wywiadowczej Cracking the Coding.

public static boolean isUniqueChars2(String str) { 
    boolean[] char_set = new boolean[256]; 
    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; 
} 

i autor wspomina, że ​​

Czas złożoność wynosi O (n), gdzie n oznacza długość łańcucha, a przestrzeń złożoność wynosi O (n).

Rozumiem czasową złożoność jest O (n), ale nie rozumiem, jak może być przestrzeń złożoność O (n)

Moje myślenie: char_set pozostanie tablica rozmiarów 256 bez względu na rozmiar wejściowy (str) wynosi. Nawet jeśli długość "str" ​​wynosi 100 000, char_set nadal jest tablicą 256 elementów. Więc pomyślałem, ponieważ wymagania pamięci dla tej funkcji nie zmieniają się wraz z rozmiarem wejścia i pozostają stałe 256, złożoność przestrzeni jest stała, tj. O (1).

Może ktoś wyjaśnić, jeśli się mylę (i dlaczego?)

Dziękuję bardzo.

Answer 1

to trochę bardziej skomplikowane, myślę:

maksymalna liczba powtórzeń zanim jakiś znak będzie napotkał dwa razy jest wielkość alfabetu łańcuch zbudowany jest skończona.

jeśli ten rozmiar jest skończony, złożoność czasu wynosi O (1), jeśli nie jest, tablica boolowska nie może mieć skończonego rozmiaru, a więc złożoność przestrzeni będzie O (n).