divide-and-conquer algorithm

Angol

Főnév

divide-and-conquer algorithm (tsz. divide-and-conquer algorithms)

(informatika) oszd meg és uralkodj

A divide and conquer (oszd meg és uralkodj) egy klasszikus algoritmikus stratégia, amelynek lényege, hogy a problémát kisebb részekre bontjuk, azokat rekurzívan megoldjuk, majd az eredményeket kombináljuk. Számos híres és hatékony algoritmus alapja ez a módszer, például Merge Sort, Quick Sort, Binary Search, Strassen mátrixszorzás, és még sok más.

Ez a technika nem csak egyszerű problémák megoldására használható, hanem olyan összetett területeken is, mint a numerikus számítások, gráfalgoritmusok, vagy geometriai problémák.

🧠 1. Alapötlet – mi az a divide and conquer?

A divide and conquer algoritmusok a következő három fő lépésből állnak:

Divide (felosztás) A problémát egy vagy több kisebb részproblémára bontjuk.
Conquer (megoldás) Rekurzívan megoldjuk ezeket a kisebb részproblémákat.
Combine (összevonás) Az alproblémák megoldásait kombináljuk, hogy megkapjuk az eredeti probléma megoldását.

🔁 2. Általános algoritmikus séma

def divide_and_conquer(problem):
    if problem is simple:
        return trivial_solution(problem)

    subproblems = divide(problem)
    subresults = [divide_and_conquer(p) for p in subproblems]
    return combine(subresults)

🧮 3. Klasszikus példák

3.1 Merge Sort

Divide: A listát két egyenlő részre osztja.
Conquer: Rekurzívan rendezi a két részt.
Combine: Két rendezett listát egyesít (merge).

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

3.2 Binary Search

Divide: A lista felét elveti minden lépésben.
Conquer: A keresés a másik felében folytatódik.
Combine: A megoldás azonnali.

def binary_search(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

3.3 Quick Sort

Divide: Választ egy „pivot” elemet, és szétválogatja a többit két részre (kisebb, nagyobb).
Conquer: Rekurzívan rendezi a két oldalt.
Combine: Az összeillesztés az összefűzés.

⏱️ 4. Időkomplexitás elemzése

Ha egy divide and conquer algoritmus:

${\textstyle n}$ méretű problémát oszt k darab, n/b méretű alproblémára,
majd az összeillesztés ${\textstyle O(n^{d})}$ időbe telik,

akkor a rekurzív időkomplexitás:

$T(n)=k\cdot T(n/b)+O(n^{d})$

Ez a Master Theorem alapján három esetbe sorolható:

Ha ${\textstyle d<\log _{b}(k)}$ , akkor ${\textstyle T(n)=\Theta (n^{\log _{b}(k)})}$
Ha ${\textstyle d=\log _{b}(k)}$ , akkor ${\textstyle T(n)=\Theta (n^{d}\log n)}$
Ha ${\textstyle d>\log _{b}(k)}$ , akkor ${\textstyle T(n)=\Theta (n^{d})}$

🧭 5. Előnyök

Előny	Magyarázat
Rekurzív gondolkodás	Természetesen leképezi a probléma szerkezetét
Párhuzamosítható	A részproblémák külön szálon is futtathatók
Hatékony	Sok esetben gyorsabb, mint az iteratív verzió
Átlátható	Tiszta, strukturált megoldást eredményez

⚠️ 6. Hátrányok

Hátrány	Magyarázat
Rekurzív hívások költsége	Nagy mélység → veremhasználat, memóriaigény
Nehéz kombinálni	A combine lépés nem mindig nyilvánvaló
Nem mindig optimális	Bizonyos problémákhoz a dinamikus programozás vagy greedy jobb

📦 7. További alkalmazások

📈 Karakterisztikus példák:

Probléma	Megoldás
Mátrix szorzás	Strassen algoritmus
Legközelebbi pontok síkban	Divide-and-conquer geometria
Inverziók száma	Merge sort bővítve
Fast Fourier Transform (FFT)	Cooley-Tukey algoritmus
Többségi elem keresése	Boyer-Moore + osztás

💡 8. Összehasonlítás más technikákkal

Technika	Jellemző
Brute-force	Minden lehetséges megoldást kipróbál
Greedy	Lokálisan optimális lépéseket választ
Dynamic Programming	Részeredmények eltárolása, átfedések
Backtracking	Kipróbál és visszalép, ha nem jó
Divide and Conquer	Részproblémákra bont, majd kombinál

🧾 9. Összefoglalás

Tulajdonság	Leírás
Módszer típusa	Rekurzív felosztásos stratégia
Lépések	Divide → Conquer → Combine
Hatékonyság	Gyakran ${\textstyle O(n\log n)}$ vagy jobb
Példák	Merge Sort, Binary Search, FFT
Skálázhatóság	Igen, könnyen párhuzamosítható
Nehézségek	Combine lépés bonyolultsága, rekurziókezelés