En yakın nokta çifti

Böl ve yönet ile en yakın nokta çiftini öğrenirsin.

En yakın nokta çifti

En yakın nokta çifti problemi, düzlemdeki noktalar arasındaki en kısa mesafeyi bulmayı hedefler. Naif yöntem her çifti deneyerek O(n²) çalışır.

Böl ve yönet yöntemi noktaları x'e göre ikiye böler, her yarıda en yakın çifti özyinelemeli bulur, sonra sınır bölgesinde kesişen çiftleri kontrol eder.

Bu yöntem O(n log n) zaman ve O(n) alan kullanır; naif yöntemden belirgin biçimde hızlıdır.

Böl ve yönet adımı

Böl ve yönet yönteminde noktaları x'e göre sıralayıp ikiye böleriz. Her yarıda en yakın çifti özyinelemeli buluruz; d bu iki yarıdan elde edilen en küçük mesafe olsun.

Sonra orta doğrusu etrafında d genişliğinde şerit alınır. Bu şeritte y noktasına göre sıralayıp her noktayı sonraki birkaç noktayla karşılaştırırız.

Şerit taraması O(n) zaman alır; toplam karmaşıklık O(n log n) olur.

Uygulama closest_pair fonksiyonu

closest_pair(points) yaz. Nokta listesindeki en yakın çiftin mesafe karesini döndür (karekök alma). print(closest_pair([(0,0), (3,4), (1,1)])) ile 2 yazdır.

Örnek çözümü göster

def closest_pair(points):
    # En yakın çiftin mesafe karesi
    n = len(points)
    best = float('inf')
    for i in range(n):
        for j in range(i + 1, n):
            dx = points[i][0] - points[j][0]
            dy = points[i][1] - points[j][1]
            d = dx * dx + dy * dy
            if d < best:
                best = d
    return best
print(closest_pair([(0,0), (3,4), (1,1)]))

Kendini test et

Naif en yakın çift yönteminin karmaşıklığı?
```
for i in range(n):
    for j in range(i+1, n):
```
- O(n)
- O(n log n)
- O(n²)
- O(1)
Cevabı göster

O(n²) — Çift iç içe döngü O(n²) çalışır.

mesafe hesabı

dx = points[i][0] - points[j][____]
dy = points[i][1] - points[j][1]

Cevabı göster

dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]

En yakın çift kavramları

naif

O(n²)
böl ve yönet

O(n log n)
mesafe karesi

Karekök yok
şerit

Orta bölge

Sıradaki ders: Nokta poligonda mı

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler