Her Karmaşıklık Sınıfı Bir Eğri Çizer
Maliyeti Giriş Büyüklüğüne Karşı Çizin
Giriş boyutunu N x eksenine koyun. Maliyeti (işlemler, zaman) y eksenine koyun. Her karmaşıklık sınıfı farklı bir eğri üretir. Bir algoritmanın büyüme hızını performans eğrisinin şeklinden tanıyabilirsiniz.
O(1) — düz yatay çizgi. f(N) = 1 işlevi. Eğim yok. Maliyet N ne olursa olsun hiçbir zaman değişmez. Karma tablo araması: tablo 10 ya da 10.000.000 eleman içeriyorsa, bir karma hesaplaması doğru kovaya atlar.
O(log N) — hafif yukarı doğru eğri, azalan eğim. N = 1.000.000'da: maliyet ≈ 20 işlem. Eğri küçük N'de keskin şekilde yükselir, ardından düzleşir. N'nin her iki katına çıkması tam olarak bir birim maliyet ekler.
O(N) — köşegen düz çizgi. Eğim = 1 (asimptotik anlamda). Maliyet N ile aynı oranda büyür. N üçe katlanırsa, maliyet de üçe katlanır.
O(N log N) — hafif yukarı doğru eğriliğe sahip daha dik köşegen. O(N)'nin üstünde ancak O(N²)'nin altında yer alır. log faktörü doğrusal eğime yavaş büyüyen bir çarpan ekler.
O(N²) — yukarı doğru açılan parabol. Eğim N büyüdükçe artar. N = 10'da: maliyet = 100. N = 100'de: maliyet = 10.000. N = 1.000'de: maliyet = 1.000.000.
Büyüyen Boşluk
O(N²) / O(N) = N oranı. Parabol ve köşegen arasındaki boşluk N büyüdükçe genişler. N = 10'da: 10× boşluk. N = 100'de: 100× boşluk. N = 1.000'de: 1.000× boşluk. N = 50.000'de: 50.000× boşluk. Boşluk daima N'ye eşittir.
Ölçek Boşluğunu Hesaplama
Büyük bir bağımlılık grafiği 50.000 paket içerir (N = 50.000). Bir algoritma O(N) zamanında çalışır. İkincisi O(N²) zamanında çalışır. Bu N'de oran O(N²)/O(N) = N = 50.000'dir.
Bir Doğru Parçasını İkiye Bölme
İkili Arama Tekrarlanan İkiye Bölme Olarak
N elemanın sıralanmış bir dizisi uzunluk N'nin bir doğru parçasını oluşturur. İkili arama bu parçayı art arda ikiye böler:
1. Kalan parçanın orta noktasına işaret edin.
2. Hedef < orta nokta ise: sağ yarı kaybolur. Sol yarı üzerinde yinelemeli olarak çalışın.
3. Hedef > orta nokta ise: sol yarı kaybolur. Sağ yarı üzerinde yinelemeli olarak çalışın.
4. Hedef = orta nokta ise: bitti.
k ikiye bölmeden sonra, kalan parça uzunluğu N / 2^k'dir. Arama bu uzunluk 1'e eşit olduğunda biter:
N / 2^k = 1 → 2^k = N → k = log₂N
Dolayısıyla N eleman üzerinde ikili arama en fazla log₂N karşılaştırması gerektirir.
İkiye Bölme & İki Katına Çıkarma: Aynı Eğrinin İki Yüzü
İkiye bölme ve iki katına çıkarma geometrik tersleridir. Üstel eğri 2^k ve logaritmik eğri log₂N, y = x doğrusu üzerinde birbirinin yansımalarıdır.
Kâğıt katlama örneğini düşünün: bir sayfa 0,1 mm kalınlıkta başlar. Her kat kalınlığı iki katına çıkarır. 42 katlamadan sonra: 0,1 mm × 2^42 ≈ 439.804 km — ayın ötesinde (384.400 km). İkili arama tersi çalışır: N elemanla başlayın, her adım sayı ikiye bölün, log₂N adımında 1 elemana ulaşın.
Geometri: ikiye bölme kendi kendine benzer bir işlemdir. Her ikiye bölme, bütüne yapı açısından aynı görünen iki yarı üretir. Yinelemeli işlemler ve logaritmalar bu kendine benzerliği paylaşırlar.
Karşılaştırmalar & İki Katına Çıkarmalar
Sıralanmış bir dizi 1.048.576 eleman içerir. Not: 1.048.576 = 2^20.
Geometrik Harita Olarak Bir Karma İşlevi
İşlev Olarak Karma İşlevi
Bir karma tablo, bir karma işlevi kullanarak bir anahtarı bir kovaya eşler:
bucket = hash(key) mod table_size
Bu, katı matematiksel anlamda bir işlevdir: bir tanım kümesini (tüm olası anahtarlar) bir değer kümesine eşler (kova indeksleri 0'dan table_size − 1'e). Geometrik resim: anahtarlar bir alanı işgal eder; kovalar başka bir alanı işgal ederler. Karma işlevi anahtarları kova indekslerine yansıtır.
O(1) araması — doğrudan atla, arama yok. Karma işlevi kova indeksini sabit zamanda hesaplar. Doğrudan bu kovaya atlayın. Geçişe yok, karşılaştırma döngüsüne yok.
Yük faktörü. Yük faktörü 0,75 olduğunda, %75 kovası en az bir eleman içerir. ~0,9'un üzerinde, çarpışmalar artar: iki anahtar aynı kovaya karma hale girer, bu kovada bir eleman zinciri oluştururlar. Uzun bir zincirde arama en kötü durumda O(N) düzeyine düşer.
Geometri Olarak Dağılım Kalitesi
İyi dağıtılmış bir karma işlevi anahtarları tüm kovalar arasında eşit şekilde yayar. Geometrik olarak: işlevin aralığı kod alanını eşit şekilde kapsar. Her kova yaklaşık olarak N / table_size anahtarı alır.
Zayıf bir karma işlevi anahtarları birkaç kovaya kümeleler. Geometrik olarak: işlevin aralığı kod alanının bir alt kümesine çöker — çoğu anahtar aynı birkaç noktaya eşlenir. Kalan kovalar boş durur.
MOAD-0001'e Bağlantı
Bir listeyi bir küme ile değiştirmek MOAD-0001'i düzeltir, çünkü bir küme dahili olarak bir karma tablo kullanır. O(N) liste taraması → O(1) karma tablo araması. Geometrik olarak: bir sıra boyunca doğrusal geçiş, bir işlev aracılığıyla doğrudan bir yansımaya dönüşür. Sıra kaybolur; işlev onu değiştirir.
Zayıf Dağıtılmış Bir Karmanın Analizi
Bir karma tablo 1.000 kovaya ve 900 elemana (yük faktörü 0,9) sahiptir. Zayıf bir karma işlevi bu elemanların 500'ünü aynı kovaya gönderir.