A számítástechnikában az algoritmusok elemzése nagyon fontos rész. Fontos megtalálni a leghatékonyabb algoritmust a probléma megoldására. Lehetséges, hogy sok algoritmus létezik egy probléma megoldására, de itt a kihívás a leghatékonyabb kiválasztása.
Most az a lényeg, hogyan ismerhetnénk fel a leghatékonyabb algoritmust, ha különböző algoritmusok állnak rendelkezésünkre? Itt jön létre az algoritmusok tér és idő komplexitásának fogalma. A tér és az idő összetettsége az algoritmusok mérési skálájaként működik. Összehasonlítjuk az algoritmusokat a tér (a memória mennyisége) és az idő bonyolultsága (a műveletek száma) alapján.
Az algoritmus által a számítógép végrehajtásakor felhasznált memória teljes mennyisége az adott algoritmus térbeli összetettsége. Ebben a cikkben nem tárgyaljuk az űrbonyolultságot (hogy ez a cikk egy kicsit kisebb legyen).
Idő komplexitás
Tehát az idő bonyolultsága azon műveletek száma, amelyeket egy algoritmus végrehajt a feladatának elvégzéséhez (tekintve, hogy minden művelet ugyanannyi időt vesz igénybe). Az algoritmust, amely a feladatot a legkevesebb művelettel hajtja végre, az idő bonyolultsága szempontjából a leghatékonyabbnak tekintjük. A tér és az idő összetettségét azonban olyan tényezők is befolyásolják, mint az operációs rendszer és a hardver, de ezeket nem vesszük bele a vitába.
Most, hogy megértsük az idő bonyolultságát, vegyünk egy példát, amelyben összehasonlítunk két különböző algoritmust, amelyeket egy adott probléma megoldására használnak.
A probléma a keresés. Meg kell keresnünk egy elemet egy tömbben (ebben a feladatban feltételezzük, hogy a tömb növekvő sorrendbe van rendezve). A probléma megoldásához két algoritmusunk van:
1. Lineáris keresés.
2. Bináris keresés.
Tegyük fel, hogy a tömb tíz elemet tartalmaz, és meg kell találnunk a tömbben a tíz számot.
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;A lineáris keresési algoritmus összehasonlítja a tömb egyes elemeit a search_digit értékkel . Ha megtalálja a tömbben a search_digit értéket , akkor igaz lesz .
Most számoljuk meg az elvégzett műveletek számát. Itt a válasz 10 (mivel összehasonlítja a tömb minden elemét). Tehát a lineáris keresés tíz műveletet használ az adott elem megkeresésére (ezek a műveletek maximális száma ennél a tömbnél; Lineáris keresés esetén ezt egy algoritmus legrosszabb esetének is nevezik).
Általában lineáris keresés fog n műveletek száma a legrosszabb esetben (ahol n az a tömb méretét).
Vizsgáljuk meg az eset bináris keresési algoritmusát.
A bináris keresés könnyen érthető a következő példával:
Forrás: Learneroo
Ha megpróbáljuk ezt a logikát alkalmazni a problémánkra, először összehasonlítjuk a keresés_digit és a tömb középső elemét, azaz az 5. Most, mivel az 5 értéke kevesebb, mint 10, akkor elkezdjük keresni a keresés_jegyet a tömb elemeiben nagyobb, mint 5, ugyanúgy, amíg meg nem kapjuk a kívánt 10 elemet.
Most próbálja megszámolni a bináris keresés által végrehajtott műveletek számát a kívánt elem megtalálásához. Körülbelül négy műveletre volt szükség. Ez volt a bináris keresés legrosszabb esete. Ez azt mutatja, hogy logaritmikus összefüggés van az elvégzett műveletek száma és a tömb teljes mérete között.
műveletek száma = log (10) = 4 (kb.)
a 2. bázishoz
Ezt az eredményt általánosíthatjuk a bináris kereséshez:
N méretű tömb esetén a bináris keresés által végrehajtott műveletek száma: log (n)
A nagy O jelölés
A fenti állításokban azt láttuk, hogy egy n méretű tömb esetén a lineáris keresés n műveletet hajt végre a keresés befejezéséhez. Másrészt a bináris keresés log (n) műveletszámot hajtott végre (mindkettő a legrosszabb esetben). Ezt ábrázolhatjuk grafikonként ( x tengely : elemek száma, y tengely : műveletek száma).
Forrás: Techtud
Az ábra alapján teljesen világos, hogy a lineáris keresésnél a komplexitás növekedési sebessége sokkal gyorsabb, mint a bináris keresésé.
Egy algoritmus elemzésénél egy jelölést használunk annak időbeli összetettségének ábrázolására, és ez a jelölés Big O jelölés.
Például: a lineáris keresés időbeli bonyolultsága O (n) és O (log n) formájában ábrázolható bináris keresés esetén (ahol n és log (n) a műveletek száma).
Néhány népszerű algoritmus időbeli összetettségét vagy Big O jelölését az alábbiakban soroljuk fel:
- Bináris keresés: O (log n)
- Lineáris keresés: O (n)
- Gyors rendezés: O (n * log n)
- Válogatás rendezése: O (n * n)
- Utazó eladó: O (n!)
Következtetés
Nagyon értékelem erőfeszítéseit, ha még mindig olvassa ezt a cikket. Most biztosan gondolkodik - miért olyan fontos megérteni az idő bonyolultságát?
Tudjuk, hogy kis számú elemnél (mondjuk 10) a bináris keresés és a lineáris keresés által végrehajtott műveletek száma közötti különbség nem olyan nagy. De a való világban legtöbbször olyan problémákkal foglalkozunk, amelyek nagy darabokkal rendelkeznek.
Például, ha 4 milliárd elem van a keresésre, akkor a legrosszabb esetben a lineáris kereséshez 4 milliárd műveletre lesz szükség a feladat elvégzéséhez. A bináris keresés ezt a feladatot mindössze 32 művelettel hajtja végre. Ez nagy különbség. Tegyük fel, hogy ha egy művelet befejezése 1 ms-ot vesz igénybe, akkor a bináris keresés csak 32 ms-ot vesz igénybe, míg a lineáris keresés 4 milliárd ms-ot vesz igénybe (ez kb. 46 nap). Ez jelentős különbség.
Ez az oka annak, hogy az időbonyolultság tanulmányozása fontossá válik, amikor ilyen nagy mennyiségű adatról van szó.
Erőforrások
Grokking algoritmusok - Aditya Y Bhargava
Bevezetés a Big O jelölésbe és az idő komplexitásába - CS Dojo