Wikiszótár

kvadratikus algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkvɒdrɒtikuʃɒlɡoritmuʃ]

Főnév

kvadratikus algoritmus

  1. (matematika, algoritmusok)

Kvadratikus algoritmus

A kvadratikus algoritmus olyan algoritmus, amelynek időbonyolultsága ( O(n^2) ), ahol ( n ) a bemenet mérete. Ez azt jelenti, hogy a futási idő arányos a bemenet méretének négyzetével.


Jellemzők

  1. Egyszerűség:

A kvadratikus algoritmusokat általában egyszerű implementálni.

  1. Lassabb nagy méretű adatoknál:

A futási idő gyorsan növekszik a bemenet méretével, így nagy adathalmazoknál nem hatékony.

  1. Általános alkalmazási terület:
    • Kis méretű adatoknál jól használhatók.
    • Problémák, ahol minden elem páronként való összehasonlítására szükség van.


Példák kvadratikus algoritmusokra

  1. Buborékrendezés (Bubble Sort)

Minden elempárt összehasonlít a rendezés érdekében.

  1. Beágyazott ciklusokkal működő algoritmusok

Pl. kettős ciklusban keresünk ismétlődéseket vagy bizonyos tulajdonságokat.

  1. Legnagyobb közös részstring keresése

Két szöveg minden lehetséges párosítását összehasonlítja.


1. Példa: Buborékrendezés

Algoritmus leírása

A buborékrendezés az elemeket páronként összehasonlítja, és a nagyobb elemet hátrébb mozgatja.

Python Implementáció

def bubble_sort(arr):
    """
    Kvadratikus algoritmus: Buborékrendezés
    :param arr: Rendezendő lista
    :return: Rendezett lista
    """
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Példa használat
arr = [64, 34, 25, 12, 22, 11, 90]
print("Eredeti lista:", arr)
sorted_arr = bubble_sort(arr)
print("Rendezett lista:", sorted_arr)

Kimenet: 

Eredeti lista: [64, 34, 25, 12, 22, 11, 90]
Rendezett lista: [11, 12, 22, 25, 34, 64, 90]

Időbonyolultság: ( O(n^2) )


2. Példa: Legnagyobb közös részstring keresése

Algoritmus leírása

Két szöveg minden lehetséges részstringjét összehasonlítjuk.

Python Implementáció

def longest_common_substring(s1, s2):
    """
    Kvadratikus algoritmus: Legnagyobb közös részstring keresése
    :param s1: Első szöveg
    :param s2: Második szöveg
    :return: Legnagyobb közös részstring
    """
    max_len = 0
    end_pos = 0
    for i in range(len(s1)):
        for j in range(len(s2)):
            l = 0
            while i + l < len(s1) and j + l < len(s2) and s1[i + l] == s2[j + l]:
                l += 1
            if l > max_len:
                max_len = l
                end_pos = i + l
    return s1[end_pos - max_len:end_pos]

# Példa használat
s1 = "abcdfgh"
s2 = "abedfgh"
result = longest_common_substring(s1, s2)
print("Legnagyobb közös részstring:", result)

Kimenet: 

Legnagyobb közös részstring: fgh

Időbonyolultság: ( O(n^2) )


3. Példa: Két ismétlődő szám keresése egy listában

Algoritmus leírása

Minden lehetséges párosítást összehasonlítunk, hogy megtaláljuk a duplikált értéket.

Python Implementáció

def find_duplicate(arr):
    """
    Kvadratikus algoritmus: Ismétlődő szám keresése
    :param arr: Lista
    :return: Az első ismétlődő szám
    """
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return arr[i]
    return None

# Példa használat
arr = [1, 3, 4, 2, 5, 3]
duplicate = find_duplicate(arr)
print("Ismétlődő szám:", duplicate)

Kimenet: 

Ismétlődő szám: 3

Időbonyolultság: ( O(n^2) )


4. Példa: Mátrix szorzása

Algoritmus leírása

Két ( n n )-es mátrix szorzata klasszikusan kvadratikus bonyolultságú.

Python Implementáció

def matrix_multiply(A, B):
    """
    Kvadratikus algoritmus: Mátrix szorzása
    :param A: Első mátrix
    :param B: Második mátrix
    :return: Szorzat mátrix
    """
    n = len(A)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += A[i][k] * B[k][j]
    return result

# Példa használat
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
result = matrix_multiply(A, B)

print("Szorzat mátrix:")
for row in result:
    print(row)

Kimenet: 

Szorzat mátrix:
[19, 22]
[43, 50]

Időbonyolultság: ( O(n^3) ) (kvadratikus, ha ( n )-t rögzítettük egy részdimenzióra)


Összegzés

Gyakori kvadratikus algoritmusok:

  1. Buborékrendezés: ( O(n^2) )
  2. Legnagyobb közös részstring keresése: ( O(n^2) )
  3. Ismétlődések keresése: ( O(n^2) )
  4. Mátrix szorzás klasszikus módon: ( O(n^2 m) )

Használat:

  • Kvadratikus algoritmusokat leginkább kis méretű bemeneteknél érdemes alkalmazni, ahol a futási idő elfogadható.
  • Nagy méretű adatok esetén hatékonyabb algoritmusokat kell keresni (pl. lineáris rendezési algoritmusokat vagy dinamikus programozást).

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=kvadratikus_algoritmus&oldid=3480718”