keresőalgoritmus

Magyar

Kiejtés

• IPA: [ ˈkɛrɛʃøːɒlɡoritmuʃ]

Főnév

keresőalgoritmus

1. (matematika, algoritmusok) A keresési algoritmusok célja, hogy megtalálják egy adott elem helyét (vagy igazolják, hogy az elem nem létezik) egy adatszerkezetben, például listában, gráfban vagy fában. Két fő típusuk van:

• Lineáris keresési algoritmusok: Az elemeket sorban ellenőrzik.
• Hierarchikus keresési algoritmusok: Az adatszerkezet szervezését kihasználva hatékonyabbak.

Fontos keresési algoritmusok

Lineáris keresés (Linear Search)

Leírás:

• Az elemeket sorban, egyesével ellenőrzi.
• Egyszerű és könnyen implementálható, de lassú nagy adathalmazok esetén.

Időbonyolultság:

• Legrosszabb eset: $O(n)$
• Legjobb eset: $O(1)$

Python példa:

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

arr = [4, 2, 7, 1, 3]
target = 7
print(linear_search(arr, target))  # Output: 2

Bináris keresés (Binary Search)

Leírás:

• Egy rendezett listában keres, a középső elemek felosztásával.
• Ha az elem kisebb a középsőnél, a bal oldalra, különben a jobb oldalra lép.

Időbonyolultság:

• Legrosszabb eset: $O(\log n)$
• Legjobb eset: $O(1)$

Python példa:

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

arr = [1, 2, 3, 4, 5, 6, 7]
target = 5
print(binary_search(arr, target))  # Output: 4

Ugrásos keresés (Jump Search)

Leírás:

• Rendezett listákra alkalmazható.
• Az elemeket „ugrásokkal” ellenőrzi, majd visszatér az előző blokkon belüli keresésre.

Időbonyolultság:

• Legrosszabb eset: $O({\sqrt {n}})$

Python példa:

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0

    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i
    return -1

arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
print(jump_search(arr, target))  # Output: 4

Interpolációs keresés (Interpolation Search)

Leírás:

• Rendezett listákra alkalmazható, ahol az elemek egyenletesen oszlanak el.
• Az indexet interpolációval határozza meg:

${\text{pos}}={\text{low}}+{\frac {(x-{\text{arr[low]}})\cdot ({\text{high}}-{\text{low}})}{{\text{arr[high]}}-{\text{arr[low]}}}}$

Időbonyolultság:

• Legrosszabb eset: $O(n)$
• Legjobb eset: $O(\log \log n)$

Python példa:

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high and target >= arr[low] and target <= arr[high]:
        pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])

        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1

    return -1

arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(interpolation_search(arr, target))  # Output: 3

Mélységi keresés (DFS - Depth First Search)

Leírás:

• Gráfokban vagy fákban keres, mélység szerint haladva.
• Rekurzióval vagy veremmel implementálható.

Időbonyolultság:

• $O(V+E)$, ahol $V$: csúcsok, $E$: élek száma.

Python példa:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}
dfs(graph, 2)  # Output: 2 0 1 3

Szélességi keresés (BFS - Breadth First Search)

Leírás:

• Gráfokban vagy fákban keres, szintenként haladva.

Időbonyolultság:

• $O(V+E)$, ahol $V$: csúcsok, $E$: élek száma.

Python példa:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}
bfs(graph, 2)  # Output: 2 0 3 1

Összegzés

Keresési algoritmusok összehasonlítása

Algoritmus	Adatszerkezet	Időbonyolultság (Legrosszabb)	Megjegyzések
Lineáris keresés	Lista	$O(n)$	Egyszerű, de lassú.
Bináris keresés	Rendezett lista	$O(\log n)$	Gyors, de rendezett adatra van szükség.
Jump keresés	Rendezett lista	$O({\sqrt {n}})$	Közepesen gyors.
Interpolációs keresés	Rendezett lista	$O(\log \log n)$	Egyenletes eloszlású adatokra hatékony.
DFS	Gráf	$O(V+E)$	Mélységi keresés gráfokban/fákban.
BFS	Gráf	$O(V+E)$	Szélességi keresés gráfokban/fákban.

Fordítások

Tartalom

angol: search algorithm (en)

További információk

• keresőalgoritmus - Értelmező szótár (MEK)
• keresőalgoritmus - Etimológiai szótár (UMIL)
• keresőalgoritmus - Szótár.net (hu-hu)
• keresőalgoritmus - DeepL (hu-de)
• keresőalgoritmus - Яндекс (hu-ru)
• keresőalgoritmus - Google (hu-en)
• keresőalgoritmus - Helyesírási szótár (MTA)
• keresőalgoritmus - Wikidata
• keresőalgoritmus - Wikipédia (magyar)