Big O jelölés példákkal magyarázva

A Big O jelölés egy adott algoritmus sebességének vagy összetettségének leírására szolgál. Ha a jelenlegi projekted előre meghatározott algoritmust igényel, akkor fontos megérteni, hogy milyen gyors vagy lassú ez a többi lehetőséghez képest.

Mi a Big O jelölés és hogyan működik?

Egyszerűen fogalmazva: a Big O jelölés megmondja az algoritmus által végrehajtandó műveletek számát. Nevét a műveletek becsült száma előtti szó szerinti "Big O" -ról kapta.

Amit a Big O jelölés nem mond meg, az az algoritmus sebessége másodpercekben. Túl sok tényező befolyásolja az algoritmus futtatásának idejét. Ehelyett a Big O jelöléssel fogja összehasonlítani a különböző algoritmusokat az elvégzett műveletek száma alapján.

A Big O megállapítja a legrosszabb futási időt

Képzeld el, hogy egy Jane nevű tanulóval vagy tanár. Meg akarja találni a nyilvántartásait, ezért egyszerű keresési algoritmust használva keresi át a tankerület adatbázisát.

Tudja, hogy az egyszerű keresés O (n) alkalommal fut. Ez azt jelenti, hogy a legrosszabb esetben minden egyes (n-vel jelölt) rekordot át kell keresnie, hogy megtalálja Jane-t.

De az egyszerű keresés futtatásakor kiderül, hogy Jane rekordjai a legelső bejegyzés az adatbázisban. Nem kell minden bejegyzést megnézned - első próbálkozásodra megtaláltad.

Ez az algoritmus O (n) időt vett igénybe? Vagy O (1) időbe telt, mert első próbálkozásra megtaláltad Jane lemezeit?

Ebben az esetben a 0 (1) a legjobb eset - szerencséd volt, hogy Jane rekordjai voltak a csúcson. De a Big O jelölés a legrosszabb esetre összpontosít, amely 0 (n) az egyszerű kereséshez. Megnyugtatás, hogy az egyszerű keresés soha nem lesz lassabb, mint az O (n) idő.

Az algoritmus futási ideje különböző ütemben növekszik

Tegyük fel, hogy az iskolai körzet adatbázisának minden elemének ellenőrzése 1 milliszekundumba kerül.

Egyszerű kereséssel, ha 10 bejegyzést kell ellenőriznie, 10 ms-ra lesz szükség. De a bináris keresési algoritmussal csak 3 elemet kell ellenőriznie, amelynek futtatása 3 ms-ot vesz igénybe.

A legtöbb esetben a keresendő listában vagy adatbázisban több száz vagy ezer elem lesz.

Ha 1 milliárd elem van, akkor az egyszerű keresés akár 1 milliárd ms-ot is igénybe vehet, vagyis 11 napot. Másrészt a bináris keresés használata a legrosszabb esetben csak 32 ms-ot vesz igénybe:

Nyilvánvaló, hogy az egyszerű keresés és a bináris keresés futási ideje közel azonos ütemben nem nő. Amint a bejegyzések listája növekszik, a bináris keresés csak egy kicsit több időt igényel. Az egyszerű keresés futási ideje exponenciálisan növekszik a bejegyzések listájának növekedésével.

Ezért olyan fontos tudni, hogy a futási idő hogyan növekszik a lista méretéhez képest. És pontosan itt olyan hasznos a Big O jelölés.

A nagy O jelölés a műveletek számát mutatja

Mint fent említettük, a Big O jelölés nem mutatja az algoritmus futtatásának idejét . Ehelyett a végrehajtandó műveletek számát mutatja. Megmondja, milyen gyorsan növekszik egy algoritmus, és lehetővé teszi, hogy összehasonlítsa másokkal.

Íme néhány általános algoritmus és futási idejük Big O jelöléssel:

Nagy O jelölés Példa algoritmusra
O (log n) Bináris keresés
Tovább) Egyszerű keresés
O (n * log n) Quicksort
O (n2) Válogatás rendezése
Tovább!) Utazó eladó

Most már annyit tud, hogy veszélyes lehet a Big O jelöléssel. Menjen ki, és kezdje el összehasonlítani az algoritmusokat.