Uzay karmaşıklığı, bir algoritmanın girdi büyüdükçe girdi dışında kullandığı ek belleğin nasıl arttığını anlatır. Hesaplarken yardımcı değişkenleri, yeni oluşturulan dizileri ve listeleri, girdinin kopyalarını ve özyinelemede çağrı yığınında açılan çerçeveleri sayarsın. Sonucu Big O gösterimiyle yazarsın: O(1), O(n), O(n²) gibi.
Zaman karmaşıklığında "kaç adım atıldı?" diye sorarsın. Uzay karmaşıklığında soru değişir: "kaç ek hücre ayrıldı?" Bu yazıda önce neyin sayılıp neyin sayılmadığını netleştirecek, sonra üç temel büyüme biçimini örneklerle göreceksin.
Girdi ile ek bellek neden ayrı sayılır?
Bir algoritmaya verilen liste, sayı ya da metin girdidir. Algoritmanın çalışırken kendi oluşturduğu her şey ise ek bellektir: yardımcı değişkenler, yeni listeler, kopyalar ve çağrı yığınındaki çerçeveler.
Küçük bir örnekle ayır. Fonksiyona parametre olarak gelen sayilar listesi girdidir. Fonksiyonun içinde kurduğun sonuc = [] listesi ise ek bellektir, çünkü girdi o listeyi sen istemeden vardı, sonucu sen ürettin.
Bu ayrım hesabın merkezinde durur. Girdi her algoritma için zaten n büyüklüğünde yer kaplar. Onu da sayarsan hangi algoritmayı incelersen incele sonuç en az O(n) çıkar ve algoritmalar arasındaki fark görünmez olur. Yalnızca ek belleğe bakınca bir algoritmanın listeyi yerinde işleyip işlemediğini ya da yeni bir kopya üretip üretmediğini ayırt edebilirsin.
Uzay karmaşıklığını hesaplarken algoritmanın aldığı girdiyi değil, girdi dışında oluşturduğu ek belleğin büyümesini takip et.
Çağrı yığınını da bu ilkeye dahil et. Özyinelemeli bir fonksiyon kendini çağırdıkça her çağrı için yığında yeni bir çerçeve açılır. Kodda hiç liste kurmasan bile, iç içe çağrı derinliği ek bellek demektir. Bu konuyu makalenin ilerleyen bölümlerinde ayrıca ele alacağız.
Big O bellek ölçümü değildir
Asimptotik hesap, bir algoritmanın belleği girdiyle birlikte hangi eğilimle büyüttüğünü söyler. Bayt ya da başka bir ölçüm değeri vermez. Sabit çarpanlar hesaba girmez: her çağrıda üç değişken tutan algoritma da bir değişken tutan algoritma da O(1)'dir. Programlama dilinin ve çalışma ortamının nesneleri nasıl sakladığı gibi ayrıntılar da bu hesabın dışında kalır. Bu yüzden iki O(n) algoritmanın gerçek bellek kullanımı birbirinden farklı olabilir. Big O'yu bir ölçüm cetveli değil, büyüme yönünü gösteren bir pusula olarak düşün.
O(1), O(n) ve O(n²) ek bellek için sezgi
Üç büyüme biçimini, girdi iki katına çıktığında ek belleğe ne olduğuyla düşünebilirsin.
- O(1): Girdi ne kadar büyürse büyüsün sayısı değişmeyen birkaç değişken tutulur. Örneğin bir sayaç ve bir geçici değer.
- O(n): Girdi kadar eleman taşıyan bir yardımcı liste ya da girdinin bir kopyası oluşturulur. Girdi iki katına çıkarsa ek bellek de yaklaşık iki katına çıkar.
- O(n²): n x n bir tablo ya da tüm çiftleri saklayan bir yapı kurulur. Örneğin n düğümlü bir graf için her düğüm çiftine bir hücre ayıran komşuluk matrisi. Girdi iki katına çıkarsa ek bellek yaklaşık dört katına çıkar.
n x n tablonun nasıl oluştuğunu kısa bir kodla görebilirsin:
n = 3
tablo = [[0] * n for _ in range(n)]
print(len(tablo))
print(len(tablo[0]))
print(len(tablo) * len(tablo[0]))Beklenen çıktı:
3
3
9Üç satır var ve her satırda üç hücre bulunuyor, toplam 9 hücre. n = 4 olduğunda 16, n = 10 olduğunda 100 hücre olur. Tablonun hücre sayısı n'in karesi gibi büyüdüğü için bu yapı O(n²) ek bellek kullanır.
Kendi sezgini dilden bağımsız bir soru setiyle sınamak istersen ücretsiz Algoritmik Düşünme Testi, algoritma mantığını ölçmek için kullanabileceğin bir araçtır.
Aynı algoritmanın üç sürümü: en büyük değeri bulmak
Aynı işi yapan üç fonksiyon, üç farklı ek bellek davranışı gösterebilir. Hepsi listedeki en büyük değeri bulur, ama her biri girdi dışında farklı miktarda bellek kurar.
def en_buyuk_dongu(liste):
en_buyuk = liste[0]
for sayi in liste:
if sayi > en_buyuk:
en_buyuk = sayi
return en_buyuk
def en_buyuk_kopya(liste):
kopya = sorted(liste) # girdiyle aynı boyda yeni liste
return kopya[-1]
def en_buyuk_ozyinelemeli(liste, i=0):
if i == len(liste) - 1:
return liste[i]
kalan = en_buyuk_ozyinelemeli(liste, i + 1)
return max(liste[i], kalan)
veri = [4, 9, 2, 7]
print(en_buyuk_dongu(veri))
print(en_buyuk_kopya(veri))
print(en_buyuk_ozyinelemeli(veri))
Beklenen çıktı:
9
9
9
Birinci sürüm yalnızca en_buyuk ve sayi değişkenlerini tutar. Liste ne kadar uzarsa uzasın bu iki değişken aynı kalır, yani ek bellek O(1).
İkinci sürüm sorted ile girdiyle aynı uzunlukta yeni bir liste kurar. Ek bellek listeyle birlikte büyür: O(n). (Burada yalnızca belleğe bakıyoruz; sıralamanın zaman maliyeti ayrı bir konu.)
Üçüncü sürümde yeni liste yoktur, ama her çağrı çağrı yığınında bir çerçeve açar. Dört elemanlı listede çağrılar i=0, i=1, i=2 ve i=3 değerleriyle iç içe girer. En derin noktada 4 çerçeve üst üste durur ve her biri kendi i ile kalan değişkenleri için bellekte yer tutar. i=3 çağrısı 7 döndürünce çerçeve boşalır; ardından i=2, i=1 ve i=0 sırayla kapanır. Yığın derinliği n ile orantılı olduğundan ek bellek O(n).
Python'da özyineleme derinliği için bir sınır vardır; sys.getrecursionlimit() bu sınırı döndürür. Çok uzun bir listede üçüncü sürüm bu sınıra takılıp RecursionError verebilir.
| Sürüm | Ek bellek nerede oluşuyor | Uzay karmaşıklığı |
|---|---|---|
| Tek değişkenli döngü | Yalnızca birkaç sabit değişken | O(1) |
| Kopya üzerinde sıralama | Girdi boyunda yeni liste | O(n) |
| Özyinelemeli (indeksli) | Çağrı yığınındaki n çerçeve | O(n) |
Bu hesap asimptotiktir: büyümenin eğilimini gösterir, gerçek bellek ölçümü vermez. Gerçek kullanım yorumlayıcıya ve nesne yapısına göre değişir.
Uzay karmaşıklığı hesabında sık yapılan üç hata
1. Her şeyi O(n) saymak
Kötü: "Listeyi dolaşıyor, o hâlde O(n)" demek. Dolaşmak zamanı belirler, belleği değil. Doğru: Döngü yalnızca birkaç değişken tutuyorsa ek bellek O(1)'dir. Önce "ne kadar yeni bellek ayrılıyor?" diye sor.
2. Dilim ve kopyaları gözden kaçırmak
Python'da liste dilimleme yeni bir liste nesnesi oluşturur; liste.copy() de öyle. Kodda tek bir köşeli parantez gibi görünür ama arkasında gerçek bir bellek ayrımı vardır.
def en_buyuk_dilimli(liste):
if len(liste) == 1:
return liste[0]
return max(liste[0], en_buyuk_dilimli(liste[1:])) # her çağrıda yeni liste
print(en_buyuk_dilimli([4, 9, 2, 7]))
Çıktı 9 olur. Ancak çağrı yığını açıkken her çerçeve kendi dilimini tutar. Uzunlukları n-1, n-2, ... 1 olan listeler aynı anda bellekte bulunur, yani toplam ek bellek O(n²) düzeyine çıkar. Önceki bölümdeki indeks parametreli sürüm aynı işi O(n) ile yapıyordu.
3. Girdiyi saymak ya da çağrı yığınını saymamak
Kötü: Fonksiyona verilen listeyi ek bellek olarak eklemek. Girdi zaten dışarıda oluşmuştur. Tersi de aynı derecede yanıltıcıdır: özyinelemeli bir fonksiyonda "yeni değişken yok, O(1)" demek. Her çağrı bir çerçeve açtığı için derinlik de belleğe yazılır.
Doğru: Girdiyi hesabın dışında tut, çağrı yığınını hesabın içine al.
Zaman ile bellek arasındaki takas
Bazı algoritmalar ek bellek harcayarak zaman kazanır, bazıları belleği az tutarak daha çok işlem yapar. Birinci gruba örnek, hesapladığı sonuçları bir sözlükte saklayan önbellek fikridir. Aynı alt problem tekrar sorulduğunda yeniden hesaplamak yerine sözlükten okursun. Bunun bedeli, sözlüğün girdiyle birlikte büyüyen ek belleğidir. İkinci grupta ise elindeki veriyi yerinde değiştirirsin. Ek bellek az kalır, ama aynı işi tekrar tekrar yapman gerekebilir.
Hangi tarafın daha değerli olduğu problemin kısıtlarına bağlıdır. Bellek darsa yerinde çalışan çözüm, süre darsa önbellekli çözüm daha uygun olabilir. İkisi de dar olabilir ve bu durumda ara bir yol aranır. Bu yüzden her durumda geçerli tek bir doğru seçim yoktur. Önemli olan, iki maliyeti de görüp kararı kısıtlara göre vermendir.
Üç soruluk karar çerçevesi: ek belleği nasıl bulursun?
Bir algoritmanın uzay karmaşıklığını çıkarırken kodu baştan sona şu üç soruyla tarayabilirsin:
- Ek bellek nerede oluşuyor? Yeni bir değişken, liste, tablo ya da fonksiyon çağrısının yığında açtığı çerçeve olabilir. Girdinin kendisini bu listeye yazma.
- Bu bellek girdiyle büyüyor mu? Girdi ne kadar büyürse büyüsün aynı kalıyorsa O(1) olur. Girdi kadar büyüyorsa O(n) olur. İki boyutlu bir tablo ya da eleman çiftleri kadar yer tutuyorsa O(n²) olur.
- Gizli bellek var mı? Dilimleme, kopyalama ve özyinelemenin çağrı yığında biriktirdiği çerçeveler kodda açıkça görünmeyebilir. Bu satırları ayrıca kontrol et.
Çerçeveyi en büyük değeri bulan üç sürüme geri uyguladığında her sürümün farklı bir soruda öne çıktığını görürsün. Tek değişkenle ilerleyen sürüm ilk iki soruda sabit kalır, ek belleği O(1) olarak çıkar. Listenin kopyasını çıkaran sürüm ikinci soruda ayrışır, çünkü kopya girdi kadar büyür. Özyinelemeli sürümün maliyeti üçüncü soruda ortaya çıkar. Kodda yeni bir liste görünmez, ama her çağrı yığında bir çerçeve açar. Böylece ilke cümlesine dönmüş olursun: ek belleğin büyümesini takip et, girdinin kendisini sayma.
Bu çerçeveyi farklı konularda yoklamak istersen ücretsiz bilgi testleri merkezindeki seviye testlerini ve algoritmik düşünme testini deneyebilirsin. Sorular, kavramları kodu okuyarak ve tahmin yürüterek uygulamana imkân verir.
Uzay karmaşıklığı, bir algoritmanın bellekte bıraktığı izi küçük bir soru listesine indirir. Bu listeyi her yeni koda uyguladıkça hesap hızlanır ve zaman karmaşıklığıyla birlikte düşünmek doğal bir alışkanlığa dönüşür.
