Big O jelölés - egyszerűen csak illusztrációkkal és videóval magyarázható

A Big O jelölést arra használják, hogy kommunikálják, milyen gyors egy algoritmus. Ez fontos lehet mások algoritmusainak értékelésekor, valamint a sajátjainak értékelésekor! Ebben a cikkben elmagyarázom, mi a Big O jelölés, és felsorolom az azt használó algoritmusok leggyakoribb futási idejét.

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

Judah fiam sok játékkal rendelkezik. Valójában egymilliárd játékot szerzett ! Meglepődne, hogy egy gyerek milyen gyorsan kaphat ennyi játékot, ha ő az első unoka a család mindkét oldalán. ??

Egyébként Júdának van egy problémája. Amikor barátai meglátogatnak és egy adott játékkal akarnak játszani, MINDIG eltarthat a játék megtalálása. Tehát egy keresési algoritmust akar létrehozni, hogy segítsen megtalálni egy adott játékot a lehető leggyorsabban. Két különböző keresési algoritmus között próbál dönteni: egyszerű keresés és bináris keresés. (Ne aggódjon, ha nem ismeri ezeket az algoritmusokat.)

A választott algoritmusnak gyorsnak és helyesnek kell lennie. Egyrészt a bináris keresés gyorsabb. És Judahnak gyakran csak körülbelül 0 másodperc van , mire barátja megunt egy játékot. Másrészt egy egyszerű keresési algoritmust könnyebb írni, és kevesebb az esély a hibák bevezetésére. Biztosan kínos lenne, ha barátja hibákat találna a kódjában! Különleges óvatosság érdekében Judah úgy dönt, hogy mindkét algoritmust 100 játék listájával időzíti.

Tegyük fel, hogy egy játék ellenőrzése 1 milliszekundumba kerül. Egyszerű kereséssel Judahnak 100 játékot kell ellenőriznie, így a keresés 100 ms-ig tart. Másrészt csak 7 játékot kell bináris kereséssel ellenőriznie (a log2 100 nagyjából 7, ne aggódjon, ha ez a matematika zavaró, mivel nem ez a cikk lényege), így a keresés 7 ms futni. De valójában a listán egymilliárd játék lesz. Ha mégis megtörténik, meddig tart az egyszerű keresés? Mennyi ideig tart a bináris keresés?

Futási idő egyszerű keresés és bináris keresés esetén, 100 elem listájával

Júda bináris keresést hajt végre egymilliárd játékkal, és ez 30 ms-ot vesz igénybe (log2 1.000.000.000 nagyjából 30). „32 ms!” azt hiszi. „A bináris keresés körülbelül 15-szer gyorsabb, mint az egyszerű keresés, mert az egyszerű keresés 100 ms-ot vett igénybe 100 elemmel, a bináris keresés pedig 7 ms-ot. Tehát az egyszerű keresés 30 × 15 = 450 ms-ot vesz igénybe, igaz? 30 másodperc alatt, amíg a barátom megunja. ” Júda úgy dönt, hogy egyszerű kereséssel jár. Ez a helyes választás?

Nem. Kiderült, hogy Júda tévedett és egy életre elveszítette barátját. ? Az egyszerű keresés futási ideje 1 milliárd tétel esetén 1 milliárd ms lesz, ami 11 nap! A probléma az, hogy a bináris keresés és az egyszerű keresés futási ideje nem nő ugyanolyan ütemben.

A futási idők nagyon különböző sebességgel nőnek! Az elemek számának növekedésével a bináris keresés futtatása kicsit több időt vesz igénybe, az egyszerű keresés azonban sokkal több időt vesz igénybe . Tehát a számok listájának növekedésével a bináris keresés hirtelen sokkal gyorsabbá válik , mint az egyszerű keresés.

Tehát Júda tévedett abban, hogy a bináris keresés mindig 15-ször gyorsabb, mint az egyszerű keresés. Ha 1 milliárd játék van, akkor ez inkább 33 milliószor gyorsabb.

Nagyon fontos tudni, hogyan növekszik a futási idő a lista méretének növekedésével. Ott jön be a Big O jelölés.

A Big O jelölés megmondja, hogy milyen gyors egy algoritmus. Tegyük fel például, hogy van egy n méretű listája . Az egyszerű keresésnek ellenőriznie kell az egyes elemeket, így n műveletet igényel . A futási idő Big O jelöléssel O ( n ).

Hol vannak a másodpercek? Nincsenek - a Big O nem adja meg másodpercek alatt a sebességet. A Big O jelölés lehetővé teszi a műveletek számának összehasonlítását. Megmondja, milyen gyorsan növekszik az algoritmus.

Tegyünk egy másik példát. Binary keresési igények jelentkezzen n ellenőrző műveletek listáját méretű n . Mennyi a futási idő Big O jelöléssel? Ez O (log n ). Általában a Big O jelölést a következőképpen írják.

Ez megmondja az algoritmus által végrehajtandó műveletek számát. Nagy O jelölésnek hívják, mert egy „nagy O” betűt tesz a műveletek száma elé.

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

Tegyük fel, hogy egyszerű kereséssel használ egy felhasználót a felhasználói adatbázisában. Tudja, hogy az egyszerű keresés O ( n ) időt igényel , ami a legrosszabb esetben azt jelenti, hogy az algoritmusnak át kell néznie az adatbázis minden felhasználóját. Ebben az esetben „aardvark213” nevű felhasználót keres. Ez az első felhasználó a listában. Tehát algoritmusának nem kellett minden bejegyzést megvizsgálnia - első próbálkozásra megtalálta. Az algoritmus O ( n ) időt vett igénybe? Vagy O (1) időbe telt, mert az első próbálkozásra megtalálta az illetőt?

Az egyszerű keresés még mindig O ( n ) időt vesz igénybe . Ebben az esetben az algoritmus azonnal megtalálta, amit keresett. Ez a legjobb eset. De a Big O jelölés a legrosszabb esetről szól . Tehát elmondhatja, hogy a legrosszabb esetben az algoritmusnak egyszer át kell tekintenie az adatbázis minden felhasználóját. Ez O ( n ) idő. Megnyugtatás - tudod, hogy az egyszerű keresés soha nem lesz lassabb, mint az O ( n ) idő.

Néhány gyakori Big O futási idő

Itt van öt nagy O futási idő, amelyekkel sokat találkozhat, a leggyorsabbtól a leglassabbig:

  • O (log n ), más néven napló idő. Példa: Bináris keresés.
  • O ( n ), más néven lineáris idő . Példa: Egyszerű keresés.
  • O ( n * log n ). Példa: Gyors rendezési algoritmus, például a quicksort.
  • O ( n2 ). Példa: Lassú rendezési algoritmus, például a kiválasztási rendezés.
  • O ( n !). Példa: Nagyon lassú algoritmus, mint az utazó eladó.

Különböző Big O futási idők megjelenítése

Tegyük fel, hogy 16 négyzetből álló rácsot rajzol, és ehhez 5 különböző algoritmus közül választhat. Az első algoritmus használata esetén O (log n ) időbe telik a rács megrajzolása. 10 műveletet hajthat végre másodpercenként. O (log n ) idővel 4 műveletre van szükség, hogy megrajzoljon egy 16 mezőből álló rácsot (a 16. napló 2. alapja 4). Tehát 0,4 másodpercbe telik a rács megrajzolása. Mi van, ha 1024 dobozt kell húznia? 1024 = 10 műveletet kell naplóznia, vagy 1 másodperc alatt megrajzol egy 1024 négyzetből álló rácsot. Ezek a számok az első algoritmust használják.

A második algoritmus lassabb: O ( n ) időt vesz igénybe . 16 doboz rajzolásához 16 műveletre van szükség, 1024 doboz rajzolásához pedig 1024 műveletre lesz szükség. Mennyi idő másodpercek alatt?

Íme, mennyi időbe telik egy rács megrajzolása a többi algoritmus számára, a leggyorsabbtól a leglassabbig:

Vannak más futási idők is, de ez az öt leggyakoribb.

Ez egyszerűsítés. A valóságban nem lehet konvertálni a Big O futási időből számos műveletre ilyen szépen, de ez jó becslés.

Következtetés

Itt vannak a főbb elvihetők:

  • Az algoritmus sebességét nem másodpercekben mérjük, hanem a műveletek számának növekedésében.
  • Ehelyett arról beszélünk, hogy az algoritmus futási ideje milyen gyorsan növekszik a bemenet méretének növekedésével.
  • Az algoritmusok futási idejét Big O jelöléssel fejezzük ki.
  • Az O (log n ) gyorsabb, mint az O ( n ), de sokkal gyorsabb lesz, ahogy a keresett elemek listája növekszik.

És itt van egy videó, amely sok mindent átfog és ebben a cikkben található.

Remélem, hogy ez a cikk több egyértelműséget hozott Önnek a Big O jelöléssel kapcsolatban. Ez a cikk a Manning Publications videotanfolyamomban levő leckére épül, Algorithms in Motion címmel. A tanfolyam Adit Bhargava csodálatos Grokking Algorithms című könyvén alapul. Ő rajzolta ki a cikk összes szórakoztató illusztrációját.

Ha a könyvek segítségével tanulsz a legjobban, szerezd be a könyvet! Ha videók révén tanulsz a legjobban, fontold meg a tanfolyamom megvásárlását. 39% kedvezményt kaphat a tanfolyamomból a „ 39carnes ” kód használatával .