Üçlü döngü
- Algoritmalar kursu
- İleri seviye
- Ders 26/56
- 4 dk
k, i, j iç içe döngüleriyle tabloyu güncellemeyi öğrenirsin.
Üçlü döngü
Algoritma üç iç içe döngü çalıştırır: dış döngü k ara düğümü, içteki iki döngü i ve j'yi dolaşır. Karmaşıklık O(n³)'tir.
Her k için tüm (i, j) çiftleri denenecek şekilde matris güncellenir. Bu yapı, tüm çiftlerin gevşetilmesini sağlar.
Ara düğüm
k, i'den j'ye giderken ara durak olarak kullanılan düğümdür. i → k → j yolu, doğrudan i → j yolundan daha kısaysa mesafe güncellenir.
Bu, tüm olası ara düğümleri deneyerek en kısa yolu bulur. Algoritma, her k için tabloyu bir kez günceller.
Uygulama relax_edge fonksiyonu
relax_edge(dist, i, j, k) yaz. min(dist[i][j], dist[i][k] + dist[k][j]) döndür. print(relax_edge(init_graph(), 0, 2, 1)) ile 4 yazdır.
Başlangıç kodu
def init_graph():
# Komşuluk matrisini döndür
return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
def relax_edge(dist, i, j, k):
# Tek bir gevşetme yapÖrnek çözüm
def init_graph():
# Komşuluk matrisini döndür
return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
def relax_edge(dist, i, j, k):
# Tek bir gevşetme yap
return min(dist[i][j], dist[i][k] + dist[k][j])
print(relax_edge(init_graph(), 0, 2, 1))Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 dış döngü değişkeni
for ____ in range(n):for k in range(n):Açıklama: k doğru.
2 Üçlü döngünün karmaşıklığı nedir?
- O(n²)
- O(n³) Doğru cevap
- O(n log n)
- O(n)
Açıklama: Üç iç içe döngü O(n³) verir.
3 Üçlü döngü: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
k |
Ara düğüm |
i |
Başlangıç |
j |
Bitiş |
n |
Düğüm sayısı |