Her Kompleksite Sınıfları Bir Kabarma Çizir
Maliyeti Kötüye Karşı Giriş Boyutunu Çiz
Giriş boyutunu N ekseninde yazın. Maliyeti (işlemler, zaman) Y ekseninde yazın. Her kompleksite sınıfı farklı bir kabarma çizir. Şekil performans çizgisinin büyüklüğüne göre algoritmanın büyüme hızını tanıyabilirsiniz.
O(1) — düz yatay çizgi. Fonksiyon f(N) = 1. Hiç yükselti yok. Maliyet N'e göre hiç değişmez. Hash tablosu arama: tablo 10 veya 10.000.000 öğeye sahip olursa olsun, bir hash hesabıyla doğru bir torbaya atlanır.
O(log N) — hafif yükselen eğri, yükselti azalır. N = 1.000.000: maliyet ≈ 20 işlem. Eğri küçük N için hızla yükselir, sonra düzleşir. N'nin iki katlanması maliyetine tam bir birim ekler.
O(N) — dikey düz çizgi. Yükselti = 1 (asimptotik olarak). Maliyet N'nin aynı hızda büyür. N üç katlanırsa, maliyet de üç katlanır.
O(N log N) — yukarı eğimli dikey eğri, hafif eğimli. O(N) üzerinde, O(N²) altında bulunur. Log faktörü, doğrusal eğim üzerine yavaş bir büyüyen katılıcı ekler.
O(N²) — yukarı açılı parabola. Yükselti N büyüdükçe artar. N = 10: maliyet = 100. N = 100: maliyet = 10.000. N = 1.000: maliyet = 1.000.000.
Büyüyen Kapa
O(N²) / O(N) oranı N'ye eşittir. Parabola ve dikey çizgi arasındaki kapa N büyüdükçe genişler. N = 10: 10 katlık kapa. N = 100: 100 katlık kapa. N = 1.000: 1.000 katlık kapa. N = 50.000: 50.000 katlık kapa. Kapa her zaman N'ye eşit olur.
Kapasite Kalkülasyonu
Büyük bağımlılık grafiği 50.000 pakete (N = 50.000) sahiptir. Bir algoritma O(N) zamanında çalışır. Diğeri O(N²) zamanında çalışır. Bu N'de O(N²)/O(N) = N = 50.000.
Bir Çizgi Parçasının Bölümü
Eşlemeli Arama ve Tekrarlanan Bölme
Sıralı bir dizi N öğeden oluşuyorsa, bu, N uzunluğunda bir çizgi parçasını temsil eder.
1. Kalan parçanın orta noktasına işaret et.
2. target < orta nokta ise: sağ yarıksız. Soldaki yarıda recursif çalış.
3. target > orta nokta: sol yarıksız. Sağıdaki yarıda recursif çalış.
4. target = orta nokta: tamamlanmış.
k bölmeden sonra kalan segmentin uzunluğu N / 2^k olur. Arama, bu uzunluğun 1'e eşit olduğu zaman sona erer:
N / 2^k = 1 → 2^k = N → k = log₂N
Bu nedenle, N öğeli bir dizi üzerinde eşlemeli arama en fazla log₂N karşılaştırma yapar.
Bölme ve Çiftleme: Aynı Eğrinin İki Yandanı
Bölme ve çiftleme geometrik tersleridür. Eksponansiyel eğri 2^k ve logaritma eğri log₂N, y = x eksenli yansımalardır.
Kağıt katlama düşünün: bir kağıt 0,1 mm kalınlığında başlar. Her katlama kalınlığı iki kat artırır. 42 katlama: 0,1 mm × 2^42 ≈ 439.804 km - aydan (384.400 km) daha uzak.
Geometri: bölme özelleşiktir. Her bölme, iki yarıyı oluşturur ve her biri bütünün yapısını aynen gösterir. Geribesleme ve logaritmler bu özelleşikliğe sahiptir.
Karşılaştırmalar ve Çiftlemeler
Sıralı bir dizi 1.048.576 öğeye sahip. Not: 1.048.576 = 2^20.
Bir Hash Fonksiyonu olarak Geometrik Harita
Hash Fonksiyonu olarak Fonksiyon
Bir hash tablosu, bir hash fonksiyonu kullanarak anahtarı bir kabloya maps eder:
kabap = hash(anahtar) mod table_size
Bu, dar bir matematiksel anlamıyla fonksiyondur: bir domain (tüm olası anahtarlar) bir aralığa (kabap indeksi 0 ila table_size - 1) maps eder. Coğrafi resim: anahtarlar bir alanı işgal eder; kabaplar başka bir alanı işgal eder. Hash fonksiyonu, anahtarları kabap indekslerine projeler.
O(1) arama - doğrudan atlayış, arama yok. Hash fonksiyonu, kabap indeksini sabit zaman içinde hesaplar. Doğrudan o kababa atlayın. Hiçbir gezinme, hiçbir karşılaştırma döngüsü yok.
Yük Oranı. Yük oranı %75 olan 75'lik kabaplar en az bir öğe içerir. %0,9'un üzerinde, sıklıkla aynı kababa iki anahtar düşer ve bu kabap içinde öğelerin bir zinciri oluşturur. Uzun bir zincirde arama, en kötü durumda O(N) olur.
Dağıtım Kalitesi olarak Coğrafya
Bir hash fonksiyonunun iyi dağıtılması, anahtarları eşit olarak tüm kabaplara yayar. Coğrafi olarak: fonksiyonun aralığı, kodomain'i dikkatlice eşit olarak kaplar. Her kabap yaklaşık olarak N / table_size anahtar alır.
Bir kötü hash fonksiyonu, anahtarları birkaç kababa toplanır. Coğrafi olarak: fonksiyonun aralığı, kodomain'inin bir kısmına çökür - çoğu anahtar aynı birkaç noktaya maps edilir. Kalan kabaplar boşta kalır.
MOAD-0001'e Bağlantı
Bir listeyi bir kümeyle değiştirmek, MOAD-0001'i düzeltir çünkü küme içsel olarak bir hash tablosu kullanır. O(N) liste taraması → O(1) hash tablosu arama. Coğrafi olarak: bir dizi boyunca doğrusal bir gezinme, bir fonksiyon tarafından doğrudan bir projeye dönüşür. Dizi kaybolur; fonksiyon onu değiştirir.
Kötü Dağılmış Bir Hash Analizi
Bir hash tablosu 1.000 kaba ve 900 öğe (yük faktörü 0,9) içerir. Kötü bir hash fonksiyonu, bu öğelerin 500'ini aynı kabaya gönderir.