Mi az a Big O jelölés?

A Big O (vagy O-notáció) egy olyan módszer, amellyel egy függvény aszimptotikus viselkedését írjuk le, és gyakran használják algoritmusok hatékonyságának elemzésére, azaz arra, hogy a futási idő vagy a memóriahasználat hogyan skálázódik a bemeneti adatok méretének növekedésével.

Főbb szempontok:

• Felső határ: Az O-notáció leírja a függvény növekedésének felső határát, figyelmen kívül hagyva a konstansokat és az alacsonyabb rendű tagokat. Ez a legrosszabb teljesítményű forgatókönyvet mutatja.
• Aszimptotikus viselkedés: Azt vizsgálja, hogy a függvény hogyan viselkedik, amikor a bemeneti adatok mérete a végtelenhez közelít.
• Algoritmusok összehasonlítása: Lehetővé teszi az algoritmusok összehasonlítását függetlenül a hardvertől vagy a programozási nyelvtől.

Gyakori összetettségi osztályok példái:

Notáció	Név	Leírás	Példa művelet az algoritmusban
O(1)	Állandó idő	A futási idő nem függ a bemeneti adatok méretétől.	Egy tömb elemének elérése index segítségével.
O(log n)	Logaritmikus idő	A futási idő logaritmikusan nő az adatok méretével.	Bináris keresés rendezett tömbben.
O(n)	Lineáris idő	A futási idő arányos az adatok méretével.	Lineáris keresés listában.
O(n log n)	Lineáris-logaritmikus idő	A futási idő arányos n * log n-nel.	Gyors rendezés (átlag), összefésüléses rendezés.
O(n^2)	Négyzetes idő	A futási idő arányos az adatok négyzetével.	Buborék rendezés, beágyazott ciklusok n elemre.
O(2^n)	Exponenciális idő	A futási idő exponenciálisan nő.	Néhány brute-force feladat, például az utazó ügynök problémája.

# O(1) példa
def get_first_element(arr):
    return arr[0] # Állandó idő, függetlenül az arr méretétől

# O(n) példa
def find_max(arr):
    max_val = arr[0]
    for element in arr: # Minden elemre iterálás
        if element > max_val:
            max_val = element
    return max_val

# O(n^2) példa
def print_pairs(arr):
    for i in arr: # Külső ciklus
        for j in arr: # Belső ciklus
            print(i, j)