Sözlükle çözüm, döndürülen veriler hariç, ne kadar ek bellek gerektirir?

Bir sözlük (kayıt tablosu) kullanımı, ek belleğe ihtiyaç duyar ve bu, eklenen benzersiz anahtarların sayısıyla orantılıdır. Eğer N benzersiz öğeniz varsa, bellek yaklaşık olarak O(N) olacaktır, çünkü her anahtar ve ona bağlı değer için alan ayrılır.

Örneğin, bir metindeki kelime tekrar sayısını saymak için bir sözlük oluşturursanız, bellek benzersiz kelime sayısının artmasıyla büyür. Ayrıca, sözlüğün kendisi genellikle hash değerlerinin saklanması ve çakışmaların yönetimi için ek maliyetler içerir, ancak genel olarak, O(N) ek bellek tahmini en pratiktir.