En İyi, En Kötü ve Ortalama Durum
Bir Algoritmayı Ölçmenin Üç Yolu
Her algoritmanın maliyeti girdisine bağlıdır. Aynı boyuttaki iki girdi çok farklı çalışma sürelerine neden olabilir. Karmaşıklık analizi bu varyasyon hakkında üç perspektifi formallaştırır.
En iyi durum — Ω (Omega): algoritmanın en hızlı şekilde bitmesini sağlayan girdi. N öğeli bir list üzerinde doğrusal arama için: Ω(1) — hedef ilk konumdadır. Bir karşılaştırma, bitti.
En kötü durum — O (Big O): algoritmanın en yavaş şekilde bitmesini sağlayan girdi. Doğrusal arama için: O(N) — hedef listenin sonunda oturmaktadır veya hiç görünmez. Her öğenin incelenmesi gerekir.
Ortalama durum — Θ (Theta): eşit dağılım varsayıldığında tüm olası girdilerin beklenen maliyeti. Hedefin N konumunun herhangi birine eşit olasılıkla yerleşebildiği doğrusal arama için: Θ(N/2) = Θ(N). 1/2 sabiti düşer çünkü Theta sıkı asimptotik büyümeyi ifade eder, tam katsayıları değil.
Neden En Kötü Durum Hakimdir
Sistemler en kötü durum için hazırlanmalıdır. Ortalama 10 ms alan ancak bazen 60 saniye alan bir veritabanı sorgusu, kullanıcıya görünen bir hatayı üretir. Mühendisler, performansın girdiden bağımsız olarak öngörülebilir kalması için en kötü durum sınırları için tasarım yaparlar. Ortalama durum analizi olasılıksal ortamlarda değere sahiptir, ancak en kötü durum analizi garantiler sağlar.
İkili Arama Durum Analizi
İkili arama yalnızca sıralanmış diziler üzerinde çalışır. Her adımda: hedefi orta noktadaki öğeyle karşılaştırın. Hedef orta noktaya eşitse, geri dönün. Hedef daha küçükse, sol yarısında yinelemeli olarak devam edin. Daha büyükse, sağ yarısında yinelemeli olarak devam edin.
Her karşılaştırma, kalan adayların yarısını ortadan kaldırır.
Hafıza Büyümesi & Zaman-Uzay Ticareti
Belleği Sayma, İşlemleri Değil
Zaman karmaşıklığı, bir algoritmanın yürüttüğü işlem sayısını ölçer. Uzay karmaşıklığı, girdisinin ötesinde ayırdığı ekstra belleği ölçer. Her ikisi de üretim sistemlerinde önemlidir: O(N²) belleği ayıran hızlı bir algoritma bir sunucuyu tüketecektir.
O(1) uzay: N'den bağımsız olarak sabit ekstra bellek. Yerinde sıralama (örneğin ekleme sıralaması) orijinal dizi içindeki öğeleri değiştirir. Dizinin ne kadar büyük olursa olsun O(1) olan bir avuç geçici değişken kullanır.
O(N) uzay: giriş boyutuna orantılı bellek. N öğeli bir dizinin bir kopyasını oluşturmak N yuva gerektirir. N dizeden oluşan bir liste içinden bir karma kümesi oluşturmak, en fazla N girişi depolar.
O(N²) uzay: N²'ye orantılı bellek. N köşeli bir grafik için bir N×N bitişiklik matrisi oluşturmak, N² hücre gerektirir. N = 10.000 köşe olduğunda, bu 10^8 girdiledir — basit bir boolean ızgarası için yüzlerce megabayt.
Zaman-Uzay Ticareti
Algoritma tasarımındaki temel hamlelerden biri: uzay için zaman, veya zaman için uzay ticareti yapın.
Hash tablolar, O(1) arama elde etmek için O(N) ekstra uzay kullanırlar. Karma tablosu olmadan, bir liste üzerinden tarama O(1) ekstra uzay ile O(N) arama elde eder. Karma tablo hızı satın almak için bellek öder.
Memoizasyon, daha önce hesaplanan sonuçları (O(N) veya daha fazla uzay) depolamak için bunları yeniden hesaplamaktan kaçınır. Memoizasyon olmadan özyinelemeli Fibonacci O(2^N) zamanında çalışır. Memoizasyon ile: O(N) zaman ve O(N) uzay. Uzay yatırımı zamanı üstel olarak küçültür.
Karma Sözlük vs Sıralanmış Liste
N sözcükten oluşan bir belgede sözcük oluşumlarını saymak için iki stratejiyi karşılaştırın:
Strateji A: bir sözlük (karma harita). Her sözcüğü ekleyin; sayısını artırın.
Strateji B: görülen sözcüklerin sıralanmış listesini tutun; eklemeden önce üyeliği kontrol etmek için ikili aramayı kullanın.
Amorti Edilmiş Analiz: Maliyeti Dağıtma
Ara Sıra Gider Ortalama Performansı Ne Zaman Mahvetmez
Bazı işlemler ara sıra pahalıdır ancak bir dizi boyunca ortalama olarak ucuzdur. Amorti edilmiş analiz, tüm dizi üzerinde işlem başına ortalama maliyeti hesaplar — tek bir işlemin en kötü durum maliyetini değil.
Dinamik dizi (Python list, Java ArrayList): 1 kapasitesinden başlar. Dolu olduğunda, kapasiteyi iki katına çıkarır. İki katına çıkarma tüm mevcut öğeleri kopyalar: bir append için O(N) çalışma. Ancak iki katına çıkarmalar nadirdir. N toplam append'den sonra, kaç toplam kopyalama işlemi oluştu?
İki katına çıkarmalar 1, 2, 4, 8, ..., N/2 boyutlarında oluşur. Kopyalama sayıları: 1 + 2 + 4 + ... + N/2. Bu, tüm N append'lar arasında N − 1 toplamına eşit olan geometrik bir seridir. Append başına ortalama kopyalar: (N − 1) / N < 1, bu yüzden O(1) amorti edilmiş append başına iki katına çıkarma başına O(N) en kötü durum maliyetine rağmen.
Amorti Edilmiş Analiz Neden Önemlidir
Ara sıra yeniden boyutlandırmak, yeniden dengelemek veya bir yapıyı sıkıştırmak için duran bir sistem, alarm veren en kötü durum bireysel işlemlerine sahip olabilir. Amorti edilmiş analiz, alarmın yanlış olduğunu ortaya koymaktadır: nadir pahalı olaylar birçok ucuzu tarafından ödenir. Amorti edilmiş maliyeti anlamak, aşırı mühendisliği önler: nadir O(N) işlemini yalnızca O(1) amorti edilmiş katkı yapan kaçınmak için karmaşıklık eklemek, boşa harcanan çalışmadır.
Daha derine gitmek: unhamming kursu, karmaşıklık analizini üretim yazılımındaki gerçek dünya kusurlarına uygular. Bkz. Eksik Bölüm: Algoritmik Karmaşıklık & MOAD-0001: Çökelti Kusuru.
Karma Tablo Amorti Edilmiş Ekleme
Bir karma tablo boş başlar ve yük faktörü 0,75'i aştığında kapasiteyi iki katına çıkarır. 1.000 öğe eklemek, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 kapasitelerinde tam olarak 10 iki katına çıkarmayı tetikler.