O jelölés

A Big O jelölés az algoritmusok összehasonlításának egy módja. Azzal hasonlítja össze őket, hogy kiszámítja, mennyi memóriára van szükségük, és mennyi időbe telik a végrehajtásuk.

A Big O jelölést gyakran használják annak meghatározására, hogy egy probléma mennyire összetett, más néven a probléma komplexitási osztálya. Paul Bachmann (1837-1920) matematikus használta először ezt a jelölést, az "Analytische Zahlentheorie" című könyvének második kiadásában, 1896-ban. Edmund Landau (1877-1938) tette népszerűvé a jelölést. Ezért amikor Landau-szimbólumokról beszélnek, akkor erre a jelölésre utalnak.

A Big O jelölés a "függvény rendje" kifejezésről kapta a nevét, amely a függvények növekedésére utal. A Big O Notation a függvény növekedési ütemének felső határát (a lehető legnagyobb összeget) keresi, vagyis azt számítja ki, hogy mennyi idő alatt lesz a bemenetből kimenet. Ez azt jelenti, hogy egy algoritmust aszerint lehet csoportosítani, hogy mennyi ideig tarthat egy olyan legrosszabb esetben, amikor minden alkalommal a leghosszabb utat választja.

A Big O egy olyan kifejezés, amely a legrosszabb forgatókönyv szerinti futási időt határozza meg, megmutatva, hogy mennyire hatékony egy algoritmus anélkül, hogy a programot egy számítógépen futtatnánk. Ez azért is hasznos, mert a különböző számítógépek különböző hardverrel rendelkezhetnek, és ezért különböző időre van szükségük a program elvégzéséhez. Mivel a Big O mindig a legrosszabb esetet feltételezi, konzisztens sebességmérést mutat: a hardvertől függetlenül az O ( 1 ) {\displaystyle O(1)} $O(1)$ mindig gyorsabban fog elkészülni, mint az O ( n ! ) {\displaystyle O(n!)} $O(n!)$ , mivel a hatékonyságuk különböző szintű.

Példák

A következő példák mindegyike Python nyelven írt kódot használ. Vegye figyelembe, hogy ez nem a Big O típusok teljes listája.

Állandó

O ( 1 ) {\displaystyle O(1)} $O(1)$ . Mindig ugyanannyi időt vesz igénybe, függetlenül a bemenettől. Vegyünk például egy olyan függvényt, amely elfogad egy egész számot (x-nek nevezve), és annak kétszeres értékét adja vissza:

def double(x): return x * 2 #Return the value of x times 2

A bemenet elfogadása után ez a függvény mindig tesz egy lépést, hogy visszaadjon egy kimenetet. Ez azért állandó, mert mindig ugyanannyi időt vesz igénybe, tehát O ( 1 ) {\displaystyle O(1)} $O(1)$ .

Lineáris

O ( n ) {\displaystyle O(n)} $O(n)$ . Növekszik a bemenet méretének megfelelően, amelyet n {\displaystyle n} jelez. Tegyük fel, hogy egy függvény n-t fogad el, és 1-től n-ig minden számot visszaad:

def count(n): i = 1 #Elkészítünk egy "i" nevű számlálót 1 értékkel while i <= n: #Míg i kisebb vagy egyenlő n-nel print(i) #Kiírja i értékét i = i + 1 #Újra definiálja i-t "i + 1 értékének".

Ha az 5 értéket adnánk meg, akkor ez az 1 , 2 , 3 , 4 , 5 {\displaystyle 1,2,3,4,5} kimeneti értéket adna ki. $1,2,3,4,5$ , amihez 5 ciklusra lenne szükség. Hasonlóképpen, ha 100-at adnánk meg, akkor 1 , 2 , 3...98 , 99 , 100 {\displaystyle 1,2,3...98,99,100} $1,2,3...98,99,100$ lenne a kimenet, amihez 100 ciklusra lenne szükség. Ha a bemenet n {\displaystyle n}, akkor az algoritmus futási ideje minden alkalommal pontosan n {\displaystyle n} ciklus, tehát O ( n ) {\displaystyle O(n)} $O(n)$ .

Factorial

O ( n ! ) {\displaystyle O(n!)} $O(n!)$ . Faktoriális mennyiségben növekszik, vagyis a felhasznált idő a bemenettel együtt masszívan növekszik. Tegyük fel például, hogy öt várost szeretnénk meglátogatni a világon, és minden lehetséges sorrendet (permutációt) látni szeretnénk. Egy algoritmus, amit a Python itertools könyvtárát használva írhatnánk, a következő:

import itertools #Importáljuk az itertools könyvtárat cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #A kiválasztott városok tömbje def permutations(cities): #Városok tömbjének felvétele bemenetként: for i in itertools. permutations(cities): #Minden egyes permutációnkhoz (az "i" változóhoz rendelve) print(i) #Kimenet i

Ez az algoritmus kiszámítja a városaink minden egyes egyedi permutációját, majd kiadja azt. A kimeneti példák a következők:

('London', 'Párizs', 'Berlin', 'Amszterdam', 'Róma') ('London', 'Párizs', 'Berlin', 'Róma', 'Amszterdam') ('London', 'Párizs', 'Amszterdam', 'Berlin', 'Róma') ... ('Róma', 'Amszterdam', 'Párizs', 'Berlin', 'London') ('Róma', 'Amszterdam', 'Berlin', 'London', 'Párizs') ('Róma', 'Amszterdam', 'Berlin', 'Párizs', 'London')

Itt a bemeneti listánk 5 elem hosszú, és minden egyes kiválasztásnál a fennmaradó lehetőségeink száma 1-gyel csökken. Más szóval az 5 bemenetünk 5 × 4 × 3 × 2 × 1 {\displaystyle 5\times 4\times 3\times 2\times 1} $5\times 4\times 3\times 2\times 1$ elemet választ (vagy 5 ! {\displaystyle 5!} $5!$ ). Ha a bemenetünk n {\displaystyle n} város hosszú, akkor a kimenetek száma n ! {\displaystyle n! } $n!$ ; más szóval, feltételezve, hogy minden permutáción végigmegyünk, O ( n ! ) {\displaystyle O(n!)} $O(n!)$ ciklusra lesz szükségünk a befejezéshez.

Little-o jelölés

A Big O szigorúbb változata a little-o. A nagy O és a little-o között az a különbség, hogy a little-o egy szigorú felső korlát: míg az O ( n ) {\displaystyle O(n)} $O(n)$ azt jelenti, hogy a befejezési idő a bemeneti méret alapján a maximumra nő, addig az o ( n ) {\displaystyle o(n)} $o(n)$ azt jelenti, hogy a befejezési idő általában ez alatt az idő alatt marad. Más szóval a Big O feltételezi, hogy minden ciklus a leghosszabb utat választja, és a folyamat a lehető leghosszabb ideig tart, míg a little-o reálisabb a tényleges futási időkkel kapcsolatban; ha a ciklusok száma egy hatoldalú kocka dobásán alapul, a Big O mindig 6-os számot feltételez, míg a little-o más számok dobásának egyenlő valószínűségét veszi figyelembe.

Kérdések és válaszok

K: Mi az a Big O jelölés?

V: A Big O jelölés a különböző függvények növekedési rátáinak összehasonlítására szolgáló módszer, amelyet gyakran használnak különböző algoritmusok hatékonyságának összehasonlítására annak kiszámításával, hogy mennyi memória és idő szükséges a teljesítéshez. Arra is használható, hogy megállapítsuk, mennyire összetett egy probléma.

K: Ki használta először ezt a jelölést?

V: Paul Bachmann (1837-1920) matematikus használta először ezt a jelölést 1896-ban megjelent "Analytische Zahlentheorie" című könyvében.

K: Mit jelent a Big O?

V: A Big O a "függvény rendje" rövidítése, amely a függvények növekedési sebességére utal.

K: Hogyan használják a Big O-t?

V: A Big O jelölést arra használják, hogy megtalálják a függvény növekedési ütemének felső korlátját (a lehető legnagyobb összeget), vagyis kiszámítják, hogy mennyi idő alatt lesz a leghosszabb egy bemenetből kimenet. Ez azt jelenti, hogy az algoritmusokat aszerint lehet csoportosítani, hogy a legrosszabb esetben mennyi időbe telik, ahol minden alkalommal a leghosszabb útvonalat választják.

K: Mik azok a Landau-szimbólumok?

V: A Landau-szimbólumok a Big O jelölésre utalnak, amelyet Edmund Landau (1877-1938) után neveztek el, aki ezt a jelölést népszerűvé tette.

K: Miért hasznos a Big O?

V: A Big O lehetővé teszi a sebesség mérését anélkül, hogy a programokat számítógépeken futtatnánk, mivel mindig a legrosszabb esetet feltételezi, így a számítógépek közötti hardverbeli különbségektől függetlenül konzisztens. Azt is megmutatja, hogy mennyire hatékony egy algoritmus anélkül, hogy ténylegesen futtatni kellene egy számítógépen.