Ortada Buluşma

Bazı problemlerde N yaklaşık 40 olur; tüm 2^N alt kümelerini denemek umutsuzdur. Ortadan buluşma yöntemi bu orta büyüklükteki durumları kurtarır. 🤝

Girdiyi iki yarıya bölün. Her yarıyı kaba kuvvetle çözün, ardından iki kısmi sonucu akıllıca birleştirin.

N/2 boyutundaki iki yarının her biri, toplamda 2^N yerine 2^(N/2) maliyet getirir. Bu karekök oranındaki küçülme, 2^40'ı kullanılabilir bir 2^20'ye dönüştürür.

Bir alt kümenin toplamının T hedef değerine eşit olup olmadığını sorun. N yaklaşık 40 iken alt küme toplamı, ders kitaplarındaki klasik ortadan buluşma problemidir.

Sol yarıdaki her alt kümenin toplamını listeleyip saklayın. N/2 öğeyle bu yalnızca 2^(N/2) toplamdır.

Aynı işlemi sağ yarı için yaparak tüm alt küme toplamlarının listesini oluşturun. Artık yönetilebilir iki listeniz var.

Her sağ toplam r için, T eksi r'ye eşit bir sol toplam gerekir. Bir küme veya sıralanmış liste bu kontrolü hızlandırır.

Kesin hedefler için bir karma kümesi kullanın. Sayma veya en yakın toplamlar için bir yarıyı sıralayıp üzerinde ikili arama yapın.

Toplam iş, arama veya sıralama için bir log çarpanı ile yaklaşık 2^(N/2) kadardır. N yaklaşık 40 iken işi yapılabilir kılan karmaşıklık budur.

Bir yarının tamamını sakladığınız için bellek kullanımı 2^(N/2)'ye kadar büyür. Sınır içinde kalmak için yalnızca gerekli olanları saklayın.

Alt küme toplamının yanı sıra, bir sınırın altındaki en büyük alt küme, çiftleri sayma ve ayrık logaritma türü problemler için de kullanın. Temiz bir bölme fikrini sever.

N öğeli bir alt küme problemine ortadan buluşma yöntemini uyguluyorsunuz. Yaklaşık zaman maliyeti nedir?

İki yarıya bölün, her birini kaba kuvvetle çözün, ardından sol ve sağ toplamları eşleştirin. Çok büyük bir hızlanma karşılığında az miktarda bellekten ödün verdiniz. 🚀