Bu dize manipülasyon kodunun uzay karmaşıklığı nedir?

Question

Bu kod, Kodlama röportaj kitabının çatlağından kaynaklanmaktadır.

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; 
} 

ve yazar

saat karmaşıklığı O, n dizisinin uzunluğu (n), olduğu, söz edilen ve alan karmaşıklığı O (n) 'dir.

I (n) O'dur zaman karmaşıklığını anlıyorum ama bellek karmaşıklığı O nasıl olabilir anlamıyorum (n)

Benim düşünce: CHAR_SET olursa olsun ne boyutta 256 dizisi kalacaktır giriş (str) boyutu. "str" ​​uzunluğu 100.000 olsa bile, char_set hala 256 öğe dizisidir. Bu yüzden, bu işlevin bellek gereksinimlerinin girdinin büyüklüğü ile değişmediğinden ve bir sabit 256 kalması nedeniyle, alan karmaşıklığının sabit, yani O (1) olduğunu düşündüm. Yanlış isem

birisi açıklayabilir (ve neden?)

Çok teşekkür ederim.

Answer 1

biraz daha karışık, bence: Bazı karakter iki kez karşılaştı olacak önce yineleme

maksimum sayı dizisi üzerinde inşa edilmiştir alfabesinin boyutudur.

Bu boyut sonluysa, zaman karmaşıklığı O (1) olur, eğer değilse, boole dizisi sonlu boyutta olamaz, dolayısıyla uzay karmaşıklığı O (n) olur.