Trie yapısının uzay karmaşıklığını nasıl hesaplayacağımı merak ediyorum. Derinlik(kelimenin uzunluğu) N ve Desen Boyutu K(küçük alfabeler 26 için) ve kelime sayısı ise bunu hesapladığım gibi: W Anladığım kadarıyla şöyle olmalı: K^N
Oysa birçok yerde WxKxN olduğu yazılmıştır.
Lütfen hangisinin doğru ve nasıl olduğunu detaylandırır mısınız?
En kötü durum, O(K^N) olmalıdır.
Sözcük uzunluğunun 1 olduğunu varsayalım, o zaman tek bir k boyutu dizisi yeterli olacaktır.
Ör: 'b' (konum = 1 ) k = [null, başka bir boyut dizisine işaretçi k, null, null, null,........]
Kelime uzunluğunun 2 olduğunu varsayalım, o zaman kelimedeki ilk konumda olan karakterlerin her biri için bir dizi k boyutuna sahip olmamız gerekir
Ör: 'ba'
düzey 1 ('b'): [null, bir diziye işaretçi (Z diyelim) düzey 2, null, null, null,......]
düzey 2: Z (İkinci karakter 'a'): [k, null, null, boyutundaki başka bir diziye işaretçi .......]
Diyelim ki ' bc 'ekliyoruz, sonra 3. konumda 'c' için başka bir boyut k dizisine sahip olacağız (0'da 'a', sonra 1'de 'b' Eklediğinizi varsayarak)
Bu yüzden her seviye 0, biz bir dizi boyutu k (boyutta seviye 0: K), seviye 2 Biz k dizisinin boyutu k (boyutta seviye 1: k^2), Seviye 3 biz k^2 sayı dizisinin boyutu k (boyutta seviye 3: k^3) ve benzeri.
Böylece uzay karmaşıklığı k + k^2 + k^3 + olacaktır ..... k^N (N sözcük uzunluğudur). Bu en kötü durum zaman karmaşıklığıdır.
