adatstruktúrák – algoritmusok alapjai

algoritmus egy lépésenkénti eljárás, amely meghatározza egy sor utasításokat kell végrehajtani egy bizonyos sorrendben, hogy a kívánt kimenetet. Az algoritmusok általában a mögöttes nyelvektől függetlenek, azaz egy algoritmus több programozási nyelven is végrehajtható.,

az adatstruktúra szempontjából az alábbiakban felsorolunk néhány fontos algoritmuskategóriát −

• keresési algoritmus egy elem kereséséhez egy adatstruktúrában.

• rendezési algoritmus az elemek egy bizonyos sorrendben történő rendezéséhez.

• Insert − algoritmus beszúrni elemet egy adatstruktúra.

• frissítés-algoritmus egy meglévő elem frissítéséhez egy adatszerkezetben.

• delete-algoritmus egy meglévő elem törléséhez egy adatstruktúrából.

egy algoritmus jellemzői

nem minden eljárás nevezhető algoritmusnak., Egy algoritmusnak a következő jellemzőkkel kell rendelkeznie −

• egyértelmű − az algoritmusnak egyértelműnek és egyértelműnek kell lennie. Minden lépésének (vagy fázisának), valamint bemeneteinek/kimeneteinek világosnak kell lenniük, és csak egy jelentéshez kell vezetniük.

• bemenet-egy algoritmusnak 0 vagy több jól definiált bemenettel kell rendelkeznie.

• kimenet – egy algoritmusnak 1 vagy több jól definiált kimenettel kell rendelkeznie, és meg kell egyeznie a kívánt kimenettel.

• finomság-az algoritmusoknak véges számú lépés után kell megszűnniük.,

• megvalósíthatóság-a rendelkezésre álló erőforrásokkal megvalósíthatónak kell lennie.

• Független-egy algoritmusnak lépésről-lépésre kell irányulnia, amelynek függetlennek kell lennie bármely programozási kódtól.

Hogyan írjunk algoritmust?

nincsenek jól definiált szabványok az algoritmusok írására. Inkább probléma és erőforrás-függő. Algoritmusok soha nem írt, hogy támogassa egy adott programozási kódot.

mivel tudjuk, hogy minden programozási nyelv megosztja az alapvető kódszerkezeteket, mint a hurkok (do, for, for, while), flow-control (if-else) stb., Ezek a közös konstrukciók lehet használni, hogy írjon egy algoritmus.

algoritmusokat írunk lépésről lépésre, de ez nem mindig így van. Az algoritmusírás egy folyamat, amelyet a problématartomány jól definiált definiálása után hajtanak végre. Vagyis ismernünk kell a problémás területet, amelyre megoldást tervezünk.

példa

próbáljuk meg megtanulni az algoritmusírást egy példa segítségével.

probléma-tervezzen egy algoritmust két szám hozzáadásához és az eredmény megjelenítéséhez.

Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP

algoritmusok mondják el a programozóknak, hogyan kell kódolni a programot., Alternatív megoldásként az algoritmus írható − –

Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP

algoritmusok tervezésekor és elemzésekor általában a második módszert használják egy algoritmus leírására. Ez megkönnyíti az elemző számára az algoritmus elemzését, figyelmen kívül hagyva az összes nem kívánt meghatározást. Megfigyelheti, hogy milyen műveleteket alkalmaznak, és hogyan folyik a folyamat.

lépésszámok írása, opcionális.

egy algoritmust tervezünk egy adott probléma megoldására. A probléma többféleképpen is megoldható.,

ezért számos megoldási algoritmus származtatható egy adott problémára. A következő lépés a javasolt megoldási algoritmusok elemzése, valamint a legmegfelelőbb megoldás megvalósítása.

Algoritmusanalízis

az algoritmus hatékonysága két különböző szakaszban, implementáció előtt és után is elemezhető. Ezek a következők –

• A Priori elemzés – ez egy algoritmus elméleti elemzése., Egy algoritmus hatékonyságát úgy mérjük, hogy feltételezzük, hogy minden más tényező, például a processzor sebessége állandó, és nincs hatással a megvalósításra.

• a Posterior Analysis-ez egy algoritmus empirikus elemzése. A kiválasztott algoritmus programozási nyelv használatával valósul meg. Ezt ezután a célgépen hajtják végre. Ebben az elemzésben összegyűjtjük a tényleges statisztikákat, mint például a futási idő és a szükséges hely.

megismerjük a priori algoritmus elemzését., Az algoritmuselemzés a különböző műveletek végrehajtásával vagy futási idejével foglalkozik. A művelet futási ideje a műveletenként végrehajtott számítógépes utasítások számának tekinthető.

algoritmus összetettsége

tegyük fel, hogy az X egy algoritmus, és n A bemeneti adatok mérete, az X algoritmus által használt idő és tér a két fő tényező, amelyek meghatározzák az X hatékonyságát.

• időtényező − az időt úgy mérik, hogy megszámolják a kulcsfontosságú műveletek számát, például összehasonlításokat a rendezési algoritmusban.,

• Space Factor-a tér mérése az algoritmus által megkövetelt maximális memóriaterület megszámlálásával történik.

az F(n) algoritmus összetettsége megadja az algoritmus által a bemeneti adatok méreteként szükséges futási időt és/vagy tárhelyet.

hely összetettsége

az algoritmus hely összetettsége az algoritmus által az életciklusában megkövetelt memóriaterület mennyiségét jelenti., Az algoritmus által megkövetelt hely megegyezik a következő két összetevő összegével −

• egy rögzített rész, amely bizonyos adatok és változók tárolásához szükséges hely, amelyek függetlenek a probléma méretétől. Például egyszerű változók és konstansok, programméret stb.

• a változó rész a változók által igényelt tér, amelynek mérete a probléma méretétől függ. Például dinamikus memória kiosztás, rekurziós verem tér stb.,

Tér komplexitás S(P) bármely algoritmus a P S(P) = C &plusz; SP(I), ahol C a rögzített rész, S(I) a változó része az algoritmus, ami attól függ, például jellegzetes I. alábbiakban egy egyszerű példa, hogy megpróbálja elmagyarázni a koncepció −

Algorithm: SUM(A, B)Step 1 - STARTStep 2 - C ← A + B + 10Step 3 - Stop

Itt van három változó A, B, C egy konstans. Ezért S (P) = 1 &plusz; 3. A tér az adott változók adattípusaitól és az állandó típusoktól függ, és ennek megfelelően meg kell szorozni.,

idő összetettsége

Az algoritmus idő összetettsége azt az időtartamot jelenti, amelyet az algoritmus a befejezésig futtat. Az időigényeket a T(n) numerikus függvényként lehet meghatározni, ahol a T(n) A lépések számaként mérhető, feltéve, hogy minden lépés állandó időt vesz igénybe.

például két N-bites egész szám hozzáadása n lépéseket tesz. Következésképpen a teljes számítási idő T (n) = c ∗ n, ahol c a két bit hozzáadásához szükséges idő. Itt megfigyeljük, hogy a T(n) lineárisan növekszik, ahogy a bemeneti méret nő.,