Böl ve yönet

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.

Örnek çözümü göster

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]))

Kendini test et

Merge sort'un birleştirme adımı kaç sıralı dizi alır?
- Bir
- İki
- Üç
- Dizi boyutu kadar
Cevabı göster

İki — İki

Bölme noktası

mid = (left + right) ____

Cevabı göster

mid = (left + right) // 2

Böl ve yönet: kavramları eşleştir

Böl

İkiye ayır
Birleştir

İki yarıyı sırala
Temel durum

Tek eleman
Maliyet

O(n log n)

Sıradaki ders: Merge işlemi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler