keresőalgoritmus

• IPA:

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.

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: ${\displaystyle O(n)}$
• Legjobb eset: ${\displaystyle O(1)}$

Python példa:

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

arr = 
target = 7
print(linear_search(arr, target))  # Output: 2

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: ${\displaystyle O(\log n)}$
• Legjobb eset: ${\displaystyle 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 == target:
            return mid
        elif arr < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = 
target = 5
print(binary_search(arr, target))  # Output: 4

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: ${\displaystyle 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 < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

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

arr = 
target = 9
print(jump_search(arr, target))  # Output: 4

Leírás:

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

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

Időbonyolultság:

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

Python példa:

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

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

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

    return -1

arr = 
target = 7
print(interpolation_search(arr, target))  # Output: 3

Leírás:

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

Időbonyolultság:

• ${\displaystyle O(V+E)}$, ahol ${\displaystyle V}$: csúcsok, ${\displaystyle 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:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

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

Leírás:

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

Időbonyolultság:

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

Python példa:

from collections import deque

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

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

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

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

Keresési algoritmusok összehasonlítása

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

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