Mi a Big-O jelölés?

Gondolkodott már azon, hogy egy általad írt program miért futott ilyen sokáig? Talán szeretné tudni, hogy hatékonyabbá teheti-e a kódot. A kód futtatásának megértése a kódot a következő szintre emelheti. A Big-O jelölés praktikus eszköz annak kiszámításához, hogy a kód valóban mennyire hatékony.

Mi a Big-O jelölés?

A Big-O jelölés segítségével kiszámíthatja, hogy mennyi időbe telik a kód futtatása. Fizikálisan meghatározhatja, mennyi idő alatt fut a kód, de ezzel a módszerrel nehéz elkapni a kis időbeli különbségeket. Például a 20 és 50 kódsor futtatása közötti idő nagyon kicsi. Egy nagy programban azonban ezek az eredménytelenségek összeadódhatnak.

A Big-O jelölés megszámolja, hogy egy algoritmusnak hány lépést kell végrehajtania a hatékonyságának felmérése érdekében. A kód ilyen módon történő megközelítése nagyon hatékony lehet, ha a hatékonyság növelése érdekében be kell hangolnia a kódot. A Big-O jelölés lehetővé teszi, hogy a különböző algoritmusokat a futtatáshoz szükséges lépések számával mérje, és objektíven összehasonlítsa az algoritmusok hatékonyságát.

Hogyan számolja ki a Big-O jelölést

Tekintsünk két olyan funkciót, amelyek megszámolják, hogy hány zokni van egy fiókban. Minden funkció felveszi a pár zokni számát, és visszaadja az egyes zoknik számát. A kód Pythonban van megírva, de ez nem befolyásolja azt, hogy hogyan számolnánk a lépések számát.

1. algoritmus:

def sockCounter (numberOfPairs):
individualSocks = 0
x-re a tartományban (numberOfPairs):
individualSocks = individualSocks + 2
return individualSocks

2. algoritmus:

def sockCounter (numberOfPairs):
return numberOfPairs * 2

Ez egy buta példa, és képesnek kell lennie arra, hogy könnyen megmondja, melyik algoritmus hatékonyabb. De a gyakorlat kedvéért fussunk át mindegyiken.

ÖSSZEFÜGGŐ: Mi a funkció a programozásban?

Mi a funkció a programozásban?

Ha megtanulja, hogyan programozza saját kódját, akkor meg kell értenie, hogy melyek a funkciók.

Az 1. algoritmusnak sok lépése van:

1. Nulla értéket rendel az individualSocks változóhoz.
2. Egy értéket rendel az i változóhoz.
3. Összehasonlítja az i értékét a numberOfPairs-szel.
4. Kettőt ad hozzá az individualSocks-hoz.
5. Magához rendeli az individualSocks megnövekedett értékét.
6. Egyenként növeli az i-t.
7. Ezután ugyanannyiszor visszatér a 3-6. Lépéshez, mint (indiviualSocks - 1).

Az első algoritmushoz teljesítendő lépések száma a következőképpen fejezhető ki:

4n + 2

Négy lépést kell végrehajtanunk n -szer. Ebben az esetben n egyenlő lenne a numberOfPairs értékével. Van 2 lépés is, amelyek egyszer elkészülnek.

Ehhez képest a 2. algoritmusnak csak egy lépése van. A numberOfPairs értékét megszorozzuk kettővel. Ezt kifejeznénk:

1

Ha ez még nem volt nyilvánvaló, akkor most könnyen beláthatjuk, hogy a 2. algoritmus jóval hatékonyabb.

Big-O elemzés

Általában, ha egy algoritmus Big-O jelölése érdekli, akkor jobban érdekli az általános hatékonyság és kevésbé a lépések számának finomszemcsés elemzése. A jelölés leegyszerűsítése érdekében csak megadhatjuk a hatékonyság nagyságát.

A fenti példákban a 2. algoritmust egyként fejezzük ki:

O (1)

De az 1. algoritmust leegyszerűsítjük:

Tovább)

Ez a gyors pillanatkép elárulja nekünk, hogyan kötődik az egyik algoritmus hatékonysága az n értékéhez. Minél nagyobb a szám, annál több lépést kell végrehajtania az algoritmusnak.

Lineáris kód

Mivel nem ismerjük az n értékét, hasznosabb elgondolkodni azon, hogy az n értéke hogyan befolyásolja a futtatandó kód mennyiségét. Az 1. algoritmusban elmondhatjuk, hogy a kapcsolat lineáris. Ha megrajzolja a lépések számát vs. n értéke kap egy felfelé haladó egyeneset.

Másodfokú kód

Nem minden kapcsolat olyan egyszerű, mint a lineáris példa. Képzelje el, hogy van 2D tömbje, és szeretne keresni egy értéket a tömbben. Létrehozhat egy ilyen algoritmust:

def searchForValue (targetValue, arraySearched):
foundTarget = Hamis
x-hez a tömbben
y esetén x-ben:
if (y == targetValue):
foundTarget = Igaz
return foundTarget

Ebben a példában a lépések száma függ a arraySearch tömbök számától és az egyes tömbök értékeitől. Tehát az egyszerűsített lépések száma n * n vagy n² lenne.

Ez a kapcsolat másodfokú kapcsolat, ami azt jelenti, hogy algoritmusunk lépéseinek száma n-rel exponenciálisan növekszik. Big-O jelöléssel a következőképpen írnád:

O (n²)

ÖSSZEFÜGGŐ: Hasznos eszközök a CSS-fájlok ellenőrzésére, tisztítására és optimalizálására

Logaritmikus kód

Bár sok más kapcsolat létezik, az utolsó kapcsolat, amelyet megnézünk, a logaritmikus kapcsolatok. A memória frissítéséhez egy szám naplója az a hatványérték, amely a bázisnak adott szám eléréséhez szükséges. Például:

log 2 (8) = 3

A napló háromnak felel meg, mert ha az alapunk 2, akkor 3-as kitevőre van szükségünk, hogy a 8-as számhoz érjünk.

Tehát a logaritmikus függvény kapcsolata ellentétes az exponenciális kapcsolattal. Az n növekedésével kevesebb új lépés szükséges az algoritmus futtatásához.

Első pillantásra ez ellentmondásosnak tűnik. Hogyan nőhetnek egy algoritmus lépései lassabban, mint n? Jó példa erre a bináris keresések. Vegyünk egy algoritmust egy szám keresésére egyedi értékek tömbjében.

• A keresés tömbjével kezdjük, amely a legkisebbtől a legnagyobbig terjed.
• Ezután a tömb közepén ellenőrizzük az értéket.
• Ha magasabb a számod, kizárjuk az alacsonyabb számokat a keresés során, és ha a szám alacsonyabb volt, akkor a magasabb számokat is kizárjuk.
• Most megnézzük a fennmaradó számok középső számát.
• Ismét kizárjuk a számok felét annak alapján, hogy célértékünk magasabb vagy alacsonyabb, mint a középérték.
• Addig folytatjuk ezt a folyamatot, amíg meg nem találjuk célpontunkat, vagy megállapítjuk, hogy nem szerepel a listán.

Mint látható, mivel a bináris keresések minden egyes lépésnél megszüntetik a lehetséges értékek felét, mivel n nagyobb lesz, a tömb ellenőrzésének számára gyakorolt ​​hatást alig befolyásolja. Hogy ezt Big-O jelöléssel fejezzük ki, a következőket írjuk:

O (log (n))

A Big-O jelölés fontossága

A Big-O nemzet gyors és egyszerű módot kínál arra, hogy közölje, mennyire hatékony egy algoritmus. Ez megkönnyíti a különböző algoritmusok közötti döntést. Ez különösen hasznos lehet, ha egy könyvtár algoritmust használ, és nem feltétlenül tudja, hogy néz ki a kód.

Amikor először megtanul kódolni, lineáris függvényekkel kezdi. Amint a fenti grafikonból látható, ez nagyon messzire vezet. De ahogy tapasztaltabbá válik, és elkezd összetettebb kódot építeni, a hatékonyság problémává válik. A kód hatékonyságának számszerűsítésének megértése megadja azokat az eszközöket, amelyekre szüksége van annak megkezdéséhez a hatékonyság érdekében, és mérlegelni kell az algoritmusok előnyeit és hátrányait.

10 leggyakoribb programozási és kódolási hiba

A kódolási hibák annyi problémához vezethetnek. Ezek a tippek segítenek elkerülni a programozási hibákat és megőrizni a kód értelmét.

A szerzőről