Wikiszótár

oszd meg és uralkodj algoritmus

Magyar

Kiejtés

  • IPA: [ ˈozd ˈmɛɡeːʃ ˈurɒlkoɟː ˈɒlɡoritmuʃ]

Főnév

oszd meg és uralkodj algoritmus

  1. (matematika, algoritmusok)

Oszd meg és uralkodj (Divide and Conquer) algoritmusok

Definíció

Az “oszd meg és uralkodj” egy algoritmus-tervezési paradigma, amely egy problémát kisebb részproblémákra bont, azokat rekurzívan megoldja, majd az eredményeket egyesíti az eredeti probléma megoldásához.

Lépések

  1. Felbontás (Divide): Oszd a problémát kisebb, önálló részekre.
  2. Uralkodás (Conquer): Oldd meg a részproblémákat (gyakran rekurzívan).
  3. Összeillesztés (Combine): Kombináld a részmegoldásokat a teljes probléma megoldásához.


Példák oszd meg és uralkodj algoritmusokra

1. Merge Sort (Összefésüléses rendezés)

A Merge Sort egy rendezési algoritmus, amely a listát kisebb részekre bontja, amíg csak egy elem marad, majd összeilleszti őket rendezett sorrendben.

Algoritmus lépései:
  1. Oszd fel a listát két egyenlő részre.
  2. Rekurzívan rendezd a két részlistát.
  3. Fésüld össze a két rendezett részlistát.

Python implementáció:
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # Osztás
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Összefésülés
    return merge(left, right)

def merge(left, right):
    sorted_list = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    # Maradék elemek hozzáadása
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])
    return sorted_list

# Példa
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Rendezett lista:", sorted_arr)

Kimenet:
Rendezett lista: [3, 9, 10, 27, 38, 43, 82]

2. Binary Search (Bináris keresés)

A Binary Search egy hatékony keresési algoritmus rendezett adatszerkezetekben. A keresés mindig a középső elemet hasonlítja össze a célelemmel.

Algoritmus lépései:
  1. Hasonlítsd össze a célt az aktuális intervallum középső elemével.
  2. Ha egyezik, visszatérhetsz a találattal.
  3. Ha a cél kisebb, keresd a bal oldali részt; ha nagyobb, keresd a jobb oldali részt.

Python implementáció:
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

# Példa
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(arr, target)
print("Cél elem indexe:", result)

Kimenet:
Cél elem indexe: 3

3. Quick Sort (Gyorsrendezés)

A Quick Sort egy másik rendezési algoritmus, amely a listát egy pivot elem köré rendezi, majd rekurzívan rendez kisebb és nagyobb elemeket.

Algoritmus lépései:
  1. Válassz egy pivot elemet.
  2. Helyezd el az összes kisebb elemet a pivot bal oldalára, és az összes nagyobb elemet a jobb oldalára.
  3. Rekurzívan rendezd a két alrészt.

Python implementáció:
def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# Példa
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = quick_sort(arr)
print("Rendezett lista:", sorted_arr)

Kimenet:
Rendezett lista: [3, 9, 10, 27, 38, 43, 82]

4. Strassen’s Matrix Multiplication (Strassen-féle mátrixszorzás)

A mátrixszorzást is hatékonyabbá lehet tenni az “oszd meg és uralkodj” módszerrel. Strassen algoritmusa kisebb mátrixokra bontja a problémát, és kevesebb szorzást használ.

Algoritmus lépései:
  1. Oszd fel a mátrixokat négy egyenlő méretű al-mátrixra.
  2. Számolj ki 7 speciális mátrixszorzást az al-mátrixokkal.
  3. Kombináld az al-mátrixokat az eredeti mátrixhoz.

Python implementáció:
import numpy as np

def strassen_multiply(A, B):
    if len(A) == 1:
        return A * B

    # Mátrixok felosztása
    n = len(A) // 2
    A11, A12, A21, A22 = A[:n, :n], A[:n, n:], A[n:, :n], A[n:, n:]
    B11, B12, B21, B22 = B[:n, :n], B[:n, n:], B[n:, :n], B[n:, n:]

    # Strassen-féle szorzatok
    M1 = strassen_multiply(A11 + A22, B11 + B22)
    M2 = strassen_multiply(A21 + A22, B11)
    M3 = strassen_multiply(A11, B12 - B22)
    M4 = strassen_multiply(A22, B21 - B11)
    M5 = strassen_multiply(A11 + A12, B22)
    M6 = strassen_multiply(A21 - A11, B11 + B12)
    M7 = strassen_multiply(A12 - A22, B21 + B22)

    # Eredmény mátrix összeállítása
    C11 = M1 + M4 - M5 + M7
    C12 = M3 + M5
    C21 = M2 + M4
    C22 = M1 - M2 + M3 + M6

    # Mátrix összeillesztése
    C = np.vstack((np.hstack((C11, C12)), np.hstack((C21, C22))))
    return C

# Példa
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
C = strassen_multiply(A, B)
print("Mátrix szorzat eredménye:\n", C)

Kimenet:
Mátrix szorzat eredménye:
 [[19 22]
  [43 50]]

Összegzés

Az “oszd meg és uralkodj” algoritmusok hatékonyan alkalmazhatók számos problémára, például rendezésre, keresésre és mátrixműveletekre. Ez a megközelítés a kisebb részproblémák újrafelhasználásával csökkenti a számítási költségeket, miközben rekurzív természetével egyszerűsíti a megvalósítást.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=oszd_meg_és_uralkodj_algoritmus&oldid=3479766”