Böl ve yönet
- Algoritmalar kursu
- Orta seviye
- Ders 1/80
- 4 dk
Diziyi ikiye bölüp her yarıyı sıralayıp birleştiren yöntemi öğrenirsin.
Böl ve yönet
Böl ve yönet (divide and conquer), bir problemi küçük parçalara bölmek, her parçayı ayrı çözmek ve sonuçları birleştirmektir. Merge sort bu yaklaşımın klasik örneğidir.
Diziyi ortadan ikiye böleriz, her yarıyı ayrı sıralarız, sonra sıralı iki yarıyı birleştiririz (merge). Her adımda problem yarıya iner, bu yüzden derinlik log n kadardır.
Bu yapı, recursion ile doğal biçimde ifade edilir: temel durum tek elemanlı dizidir ve zaten sıralıdır.
Bölmenin maliyeti
Diziyi ikiye bölmek ucuzdur: sadece mid = (left + right) // 2 hesaplanır ve sol-sağ yarılar recursion'a verilir. Bölme kendisi O(1) iştir.
Ağacın her düzeyinde toplam n eleman işlenir (birleştirme adımında). Düzey sayısı log n olduğundan toplam iş O(n log n) olur.
Bu, en kötü durumda bile geçerlidir; merge sort her zaman O(n log n) çalışır.
Uygulama Böl ve listele
split_half(arr) yaz. Diziyi mid = len(arr)//2 ile ikiye böl ve (left, right) demetini döndür. print(split_half([4, 2, 7, 1, 9])) ile ([4, 2], [7, 1, 9]) yazdır.
Başlangıç kodu
def split_half(arr):
# Diziyi ikiye bölÖrnek çözüm
def split_half(arr):
# Diziyi ikiye böl
mid = len(arr) // 2
return arr[:mid], arr[mid:]
print(split_half([4, 2, 7, 1, 9]))Beklenen çıktı
([4, 2], [7, 1, 9])
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Merge sort'un birleştirme adımı kaç sıralı dizi alır?
- Bir
- İki Doğru cevap
- Üç
- Dizi boyutu kadar
Açıklama: İki
2 Bölme noktası
mid = (left + right) ____mid = (left + right) // 2Açıklama: // 2 doğru.
3 Böl ve yönet: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Böl |
İkiye ayır |
Birleştir |
İki yarıyı sırala |
Temel durum |
Tek eleman |
Maliyet |
O(n log n) |