← 9. Optimalizációs alapok

9.2 Big O notation junioroknak – csak amennyi kell

Áttekintő

Hallottál már a Big O notationről? Lehet, hogy az iskolában érintettük, lehet, hogy interjún kérdezik, és nem tudtad mit válaszolni. Vagy hallottad, de nem érted, mire jó a való életben.

Ez az alfejezet nem akadémiai matematika. Nem fogunk levezetéseket csinálni, nem kell képleteket memorizálni. Egyetlen célja van: megtanulj felismerni, mikor lassítja a saját kódod önmagát – és miért.

A Big O notation egy eszköz. Egy fogalomkészlet, amellyel el tudod mondani, hogy egy kód "gyorsul-e, ha több adattal dolgozik, vagy lassul". Ez az egyetlen dolog, amit juniorként tudnod kell róla.

Részletes leírás

Mi az a Big O notation?

A Big O notation azt írja le, hogy egy algoritmus futási ideje hogyan változik az inputméret növekedésével.

Az "inputméret" lehet:

• lista hossza
• adatbázis rekordok száma
• fájl sorok száma
• bármilyen adat, amin az algoritmus dolgozik

A jelölés így néz ki: O(valami) – ahol a "valami" leírja az összefüggést.

Nem abszolút számokat ad meg (pl. "10 millisecundum"). Azt mondja meg: ha az input kétszer akkora lesz, a futási idő menyivel nő?

A három legfontosabb kategória

O(1) – Konstans idő

Mit jelent: Az input méretétől függetlenül mindig ugyanannyi idő alatt fut le.

Gondolj rá úgy: nem számít, hogy 10 vagy 10 millió elem van a listában – a művelet ugyanolyan gyors.

Példa:

# Python
def get_first(items):
    return items[0]  # O(1) - nem számít a lista mérete

// JavaScript
function getFirst(items) {
    return items[0];  // O(1)
}

// PHP
function getFirst($items) {
    return $items[0];  // O(1)
}

Más O(1) példák:

• Szótárból / hashmap-ből érték lekérése kulcs alapján
• Változóba értéket írni
• Tömb utolsó elemét lekérni (ha ismerjük a hosszát)

Az interjún: "O(1) azt jelenti, hogy konstans időben fut – az inputméret nem befolyásolja."

O(n) – Lineáris idő

Mit jelent: Ha kétszer akkora az input, kétszer annyi ideig fut.

Gondolj rá: végig kell menni minden elemen egyszer.

Példa:

# Python
def find_max(numbers):
    max_val = numbers[0]
    for num in numbers:  # minden elemet megvizsgálunk egyszer → O(n)
        if num > max_val:
            max_val = num
    return max_val

// JavaScript
function findMax(numbers) {
    let maxVal = numbers[0];
    for (let num of numbers) {  // O(n)
        if (num > maxVal) maxVal = num;
    }
    return maxVal;
}

Más O(n) példák:

• Lista összes elemének kiírása
• Tömb összes elemének összeadása
• Keresés rendezetlen listában

Fontos: Ha két egymás utáni (nem egymásba ágyazott) ciklus fut le, az is O(n) – nem O(2n), mert a konstansokat eldobjuk.

O(n²) – Négyzetes idő

Mit jelent: Ha kétszer akkora az input, négyszer annyi ideig fut. Ha 10x akkora, 100x annyi ideig.

Gondolj rá: minden elemhez meg kell nézni az összes többi elemet.

Példa:

# Python - egymásba ágyazott ciklusok
def find_duplicates_slow(items):
    duplicates = []
    for i in range(len(items)):
        for j in range(i + 1, len(items)):  # minden elemhez végigmegyünk az összesen
            if items[i] == items[j]:
                duplicates.append(items[i])
    return duplicates

// JavaScript
function findDuplicatesSlow(items) {
    const duplicates = [];
    for (let i = 0; i < items.length; i++) {
        for (let j = i + 1; j < items.length; j++) {  // belső ciklus = O(n²)
            if (items[i] === items[j]) duplicates.push(items[i]);
        }
    }
    return duplicates;
}

A veszély: 100 elemre 10.000 összehasonlítás. 10.000 elemre 100.000.000. Ez az a pont, ahol az alkalmazás "hirtelen nagyon lassú lesz, ha kicsit több adat jön".

Hogyan ismerd fel a saját kódodban?

Gyors ökölszabályok:

Amit keress:

# FIGYELMEZTETÉS: ez O(n²)
for item in big_list:           # külső ciklus: n
    for other in big_list:      # belső ciklus: n
        if item == other:       # n × n = n²
            ...

# Ugyanez O(n)-re javítva
seen = set()  # szótár/halmaz: O(1) keresés
for item in big_list:
    if item in seen:  # O(1) a set-ben
        ...
    seen.add(item)

Mit jelent ez a pratikában?

Juniorként nem fogsz minden nap Big O elemzést végezni. De felismerni kell, mikor fogsz probléma elé nézni:

• 100 rekordra gyors a kód? Kipróbálod 10.000-rel?
• Ha lassul, valószínűleg O(n²) vagy rosszabb van benne
• A legtöbb "hirtelen lassú lett az applikáció" probléma mögött egymásba ágyazott ciklus vagy N+1 query van (lásd 9.3 alfejezet)

Az interjún: Nem várják el, hogy fejből elemezel komplex algoritmusokat. De ha megkérdezik egy egyszerű kódrészletnél – tudd megmondani, hogy "ez O(n²), mert egymásba ágyazott ciklus van, és érdemes lenne set-tel O(n)-re hozni".

Amit NEM kell tudnod (juniorként)

• O(log n) – bináris keresés, rendezett adatszerkezetek (ezt is jó tudni, de nem alapkövetelmény)
• O(n log n) – hatékony rendezési algoritmusok (quicksort, mergesort)
• Matematikai bizonyítások, Θ és Ω jelölések
• Amortizált komplexitás
• NP-hard problémák

Ha valaki ilyen mélységig kérdez egy junior interjún – ritka, és általában elvárják, hogy "nem tudom pontosan" válasz is elfogadható.

Életszerű példák

Példa 1: A lassú keresés

Egy webes adminfelületen van egy "Megtalálja-e a user a termékek között?" gomb. Fejlesztés közben 50 termék volt – gyors volt. Production-ba kerülve 50.000 termék lett, és a gomb 30 másodpercig tölt.

A kód:

def user_has_purchased(user_orders, product_list):
    for order in user_orders:          # O(n)
        for product in product_list:   # O(m) - ez a belső ciklus
            if order.product_id == product.id:
                return True
    return False

Ez O(n × m) – ha mindkettő nagy, megsüllyed. Javítás:

def user_has_purchased(user_orders, product_list):
    product_ids = {p.id for p in product_list}  # set, O(m) egyszer
    for order in user_orders:                    # O(n)
        if order.product_id in product_ids:      # O(1) lookup
            return True
    return False

Eredmény: O(n + m) – sokkal gyorsabb nagy adaton.

Példa 2: Az interjúkérdés

Interjún megmutatnak egy kódrészletet:

function hasDuplicate(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (i !== j && arr[i] === arr[j]) return true;
        }
    }
    return false;
}

Kérdés: "Mit gondolsz erről a kódról?"

Helyes válasz: "Ez O(n²) komplexitású, mert egymásba ágyazott két ciklus fut végig az összes elemen. Nagy inputon nagyon lassú lesz. Egy Set-tel O(n)-re lehetne hozni – egyszer végigmegyünk, és minden elemet berakunk egy Set-be, ha már benne van, duplikátum."

Ez a válasz megmutatja, hogy értesz a kód viselkedéséhez – ez az, amit keresnek.

Példa 3: A napi fejlesztői döntés

Kapsz egy ticket-et: "Szűrjük ki azokat a usereket, akiknek van aktív előfizetésük."

Rossz megoldás (ha sok user van):

active_users = []
for user in all_users:                    # O(n)
    for sub in all_subscriptions:         # O(m) - minden userhez!
        if sub.user_id == user.id and sub.active:
            active_users.append(user)
            break

Jobb megoldás:

# Előbb csináljunk egy gyors lookup struktúrát
active_user_ids = {
    sub.user_id 
    for sub in all_subscriptions 
    if sub.active
}  # O(m) egyszer

active_users = [
    user for user in all_users 
    if user.id in active_user_ids  # O(1) lookup
]  # O(n)

Eredmény: O(n + m) az O(n × m) helyett.

Tesztfeladatok

1. feladat – Felismerés

Mi a következő kód komplexitása? Indokold meg!

def sum_all(numbers):
    total = 0
    for n in numbers:
        total += n
    return total

a) O(1)
b) O(n)
c) O(n²)
d) O(log n)

2. feladat – Egymásba ágyazott ciklusok

Mi a következő kód komplexitása?

function printPairs(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

a) O(1)
b) O(n)
c) O(n²)
d) O(2n)

3. feladat – Szótár keresés

Mi a különbség a komplexitásban a két kód között?

Kód A:

def find_user(users_list, user_id):
    for user in users_list:  # lista átvizsgálás
        if user["id"] == user_id:
            return user
    return None

Kód B:

def find_user(users_dict, user_id):
    return users_dict.get(user_id)  # szótár keresés

4. feladat – Rangsorolás

Rangsorold sebesség szerint (leggyorsabbtól leglassabbig) nagy inputon:

• O(n²)
• O(1)
• O(n)

5. feladat – Javítás

Az alábbi kód O(n²) komplexitású. Hogyan javítanád O(n)-re?

def remove_duplicates(items):
    result = []
    for item in items:
        if item not in result:  # ez lista keresés = O(n)!
            result.append(item)
    return result

Tipp: Gondolj arra, milyen adatstruktúra teszi O(1)-re a "benne van-e?" kérdést.

def remove_duplicates(items):
    seen = set()   # set: O(1) keresés
    result = []
    for item in items:
        if item not in seen:   # O(1)
            result.append(item)
            seen.add(item)
    return result

6. feladat – Valódi szituáció

Csapattársad írt egy kódot, ami 200 felhasználóval tökéletesen működik. De production-ban 50.000 felhasználó van, és az oldal 40 másodpercig tölt.

def get_active_premium_users(all_users, premium_ids, active_ids):
    result = []
    for user in all_users:
        for pid in premium_ids:
            if user.id == pid:
                for aid in active_ids:
                    if user.id == aid:
                        result.append(user)
    return result

Kérdések:

1. Mi a kód komplexitása?
2. Miért volt gyors 200 felhasználóval?
3. Hogyan javítanád?

def get_active_premium_users(all_users, premium_ids, active_ids):
    premium_set = set(premium_ids)  # O(p) egyszer
    active_set = set(active_ids)    # O(a) egyszer
    
    return [
        user for user in all_users          # O(n)
        if user.id in premium_set           # O(1)
        and user.id in active_set           # O(1)
    ]

7. feladat – Mikor számít?

Melyik esetben nem szükséges foglalkozni az O(n²) komplexitással?

a) Egy listán keresel, amiben mindig pontosan 5 elem van
b) Egy listán keresel, ami production-ban 100.000 elemet tartalmaz
c) Egy belső ciklus fut, ami minden API kérésnél lefut
d) A kód csak fejlesztői eszközben fut, nem production-ban