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.
A kvadratikus algoritmusokat általában egyszerű implementálni.
A futási idő gyorsan növekszik a bemenet méretével, így nagy adathalmazoknál nem hatékony.
Minden elempárt összehasonlít a rendezés érdekében.
Pl. kettős ciklusban keresünk ismétlődéseket vagy bizonyos tulajdonságokat.
Két szöveg minden lehetséges párosítását összehasonlítja.
A buborékrendezés az elemeket páronként összehasonlítja, és a nagyobb elemet hátrébb mozgatja.
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 > arr:
arr, arr = arr, arr
return arr
# Példa használat
arr =
print("Eredeti lista:", arr)
sorted_arr = bubble_sort(arr)
print("Rendezett lista:", sorted_arr)
Kimenet:
Eredeti lista: Rendezett lista:
Időbonyolultság: ( O(n^2) )
Két szöveg minden lehetséges részstringjét összehasonlítjuk.
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 == s2:
l += 1
if l > max_len:
max_len = l
end_pos = i + l
return s1
# 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) )
Minden lehetséges párosítást összehasonlítunk, hogy megtaláljuk a duplikált értéket.
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 == arr:
return arr
return None
# Példa használat
arr =
duplicate = find_duplicate(arr)
print("Ismétlődő szám:", duplicate)
Kimenet:
Ismétlődő szám: 3
Időbonyolultság: ( O(n^2) )
Két ( n n )-es mátrix szorzata klasszikusan kvadratikus bonyolultságú.
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 = * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
result += A * B
return result
# Példa használat
A = , ]
B = , ]
result = matrix_multiply(A, B)
print("Szorzat mátrix:")
for row in result:
print(row)
Kimenet:
Szorzat mátrix:
Időbonyolultság: ( O(n^3) ) (kvadratikus, ha ( n )-t rögzítettük egy részdimenzióra)