En yakın nokta çifti
- Algoritmalar kursu
- Uzman seviye
- Ders 22/41
- 4 dk
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.
Başlangıç kodu
def closest_pair(points):
# En yakın çiftin mesafe karesiÖrnek çözüm
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)]))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 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²) Doğru cevap
- O(1)
Açıklama: Çift iç içe döngü O(n²) çalışır.
2 mesafe hesabı
dx = points[i][0] - points[j][____]
dy = points[i][1] - points[j][1]dx = points[i][0] - points[j][0]
dy = points[i][1] - points[j][1]Açıklama: x bileşeni 0. indekstir.
3 En yakın çift kavramları
| Kavram | Anlamı |
|---|---|
naif |
O(n²) |
böl ve yönet |
O(n log n) |
mesafe karesi |
Karekök yok |
şerit |
Orta bölge |