divide-and-conquer algorithm

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

1. (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.

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

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

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

    subproblems = divide(problem)
    subresults = 
    return combine(subresults)

• 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)
    right = merge_sort(arr)
    return merge(left, right)

• 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 == target:
        return mid
    elif arr > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

• 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.

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:

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

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

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

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

1. Rendezés X szerint
2. Felosztás két részre
3. Egyenként megoldás keresése (rekurzió)
4. Két fél között középsáv vizsgálata

Időkomplexitás:

$${\displaystyle T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n)}$$

• divide-and-conquer algorithm - Szótár.net (en-hu)
• divide-and-conquer algorithm - Sztaki (en-hu)
• divide-and-conquer algorithm - Merriam–Webster
• divide-and-conquer algorithm - Cambridge
• divide-and-conquer algorithm - WordNet
• divide-and-conquer algorithm - Яндекс (en-ru)
• divide-and-conquer algorithm - Google (en-hu)
• divide-and-conquer algorithm - Wikidata
• divide-and-conquer algorithm - Wikipédia (angol)