Táblázat megtekintése az 1-nél, Navigációs menü

Algoritmusok műveletigényének tipikus nagyságrendjei 1.

Tehetséggondozás az informatikában - Táblázatkezelés / Függvények /3. Tömbképletek

Algoritmusok műveletigénye Az ismertetésre kerülő adatszerkezeteket és algoritmusokat mindig jellemezzük majd a hatékonyság szempontjából. Az adatszerkezetek egyes ábrázolásairól megállapítjuk a helyfoglalásukat, az algoritmusoknál pedig a műveletigényt becsüljük, mindkettőt az input adatok méretének függvényében. Általában megelégszünk mindkét adat nagyságrendben közelítő értékével.

A nagyságrendi értékek közelítő ereje annál nagyobb, minél nagyobb méretű adatokra értelmezzük azokat. Amint látjuk majd, egy sajátos matematikai határérték-fogalmat vezetünk be és alkalmazunk a hatékonyságra irányuló számításainkban. A műveletigény számításakor eleve azzal a közelítéssel élünk, hogy csak az algoritmus meghatározó műveleteit vesszük számításba. Egy műveletet meghatározónak dominánsnak mondunk, ha a többihez képest jelentős a végrehajtási ideje, valamint a végrehajtásainak száma.

Téma megtekintése - Táblázatkezelés | Magyar phpBB Közösség

Általában kijelölhető egyetlen meghatározó művelet, amelyre a számítást elvégezzük. A műveletigényt a kiszemelt művelet végrehajtásainak számával adjuk meg, mivel az egyes műveletek végrehajtási ideje gépről-gépre változhat.

A lépésszám közelítéssel kiszámolt nagyságrendje — gyakorlati tapasztalatok szerint is — jól jellemzi az algoritmus tényleges futási idejét. A buborékrendezés műveletigénye A rendezés általános feladata jól ismert. A tömbökre megfogalmazott változat egyik legkorábbi kevéssé hatékony megoldása a buborékrendezés. Az eljárás működésének alapja a szomszédos elemek táblázat megtekintése az 1-nél, amennyiben az elől álló nagyobb, mint az utána következő.

Információk kiemelése feltételes formázással

Az első menetben a szomszédos elemek cseréjével „felbuborékoltatjuk” a legnagyobb elemet a tömb végére. A következő iterációs lépésben ugyanezt tesszük az „eggyel rövidebb” tömbben, és így tovább. Utoljára még a tömb első két elemét is megcseréljük, ha szükséges. Az n—1 -edik iteráció végére elérjük, hogy az elemek nagyság szerint növekvő sorban követik egymást. A rendezés algoritmusa az 1. Az egyszerűség kedvéért a Csere műveletét nem bontottuk három értékadásra.

A kép nagyobb változata külön ablakban is megtekinthető.

A buborékrendezés algoritmusa Az algoritmus műveleteit két kategóriába sorolhatjuk. Az egyikbe tartoznak a ciklusváltozókra vonatkozó műveletek, a másikba pedig az A[ Nyilvánvaló, hogy az utóbbiak a meghatározó műveletek.

Egyrészt végrehajtásuk lényegesen nagyobb időt vesz igénybe, mint a ciklust adminisztráló utasításoké különösen, ha a tömb elemeinek mérete jelentősmásrészt mindkét utasítás a belső ciklusban van még ha a csere feltételhez kötött isígy végrehajtásukra minden iterációs lépésben sor kerülhet. Ezért az összehasonlítások, illetve a cserék számát fogjuk számolni. Ha ezt a döntést meghoztuk, érdemes az algoritmusban szereplő ciklusokat tömörebb, áttekinthetőbb formában, for-ciklusként újra felírni.

Ez a változat látható az 1. Buborékrendezés for-ciklusokkal A számolást az egyszerűség kedvéért külön-külön végezzük. Nézzük először az összehasonlítások Ö n -nel jelölt számát. A külső ciklus magja n—1 -szer hajtódik végre, a belső ciklus ennek megfelelően rendre n—1, n—2, Mivel a két szomszédos elem összehasonlítása a belső ciklusnak olyan utasítása, amely mindig végrehajtódik, ezért Az 1. Most elégedjünk meg annyival, hogy általában elegendő az, ha csak a kifejezés domináns nagyságrendű tagját tartjuk meg, az együttható elhagyásával.

Az összehasonlítások számára ennek megfelelően azt mondjuk majd, hogy értéke nagyságrendben n2 és ezt így jelöljük: Megjegyezzük, hogy az összehasonlítások száma a bemenő adatok bármely permutációjára ugyanannyi.

FKERES függvény

Az elemzett műveletek táblázat megtekintése az 1-nél száma a legtöbbször azonban változó az adatok függvényében. Ilyenkor elsősorban a végrehajtások maximális és átlagos számára vagyunk kíváncsiak, de a minimális végrehajtási számot is gyakran meghatározzuk, bár ennek általában nincs jelentősége. Ha T n -nel jelöljük a műveletigényt, akkor annak minimális, maximális és átlagos értékét rendre mT nMT n és AT n jelöli.

Vizsgáljuk meg most a cserék Cs n -nel jelölt számát.

Logaritmus

Ez a szám már nem állandó, hanem a bemenő adatok függvénye. Nevezetesen, a cserék száma megegyezik az A[ A rendezett tömbben pedig nincs inverzió. Ha a tömb eleve rendezett, akkor egyetlen cserét sem kell végrehajtani, így a cserék száma a legkedvezőbb esetben nulla, azaz Táblázat megtekintése az 1-nél legtöbb cserét akkor kell végrehajtani, ha minden szomszédos elempár inverzióban áll, azaz akkor, ha a tömb éppen fordítva, nagyság szerint csökkenő módon rendezett.

Ekkor A cserék átlagos számának meghatározásához először is feltesszük, hogy a rendezendő számok minden permutációja egyformán valószínű. Az átlagos műveletigény számításához mindig ismerni kell a bemenő adatok valószínűségi eloszlását, vagy legalább is feltételezéssel kell élni arra nézve! Az általánosság megszorítása nélkül vehetjük úgy, hogy az 1, 2, A cserék számának átlagát nyilvánvalóan úgy kapjuk, hogy az 1, 2, Az összeg meghatározásánál nehézségbe ütközünk, ha megpróbáljuk azt megmondani, hogy adott n-re hány olyan permutáció van, amelyben i számú inverzió található.

Ehelyett célszerű párosítani a permutációkat úgy, hogy mindegyikkel párba állítjuk az inverzét, pl.

Egy ilyen párban az inverziók száma együtt éppen a lehetséges -t teszi ki, pl. Az állítás igazolására gondoljuk meg, hogy egy permutációban táblázat megtekintése az 1-nél elem pontosan akkor áll inverzióban, hogy ha az inverz permutációban nincs közöttük inverzió.

Írjuk le gondolatban mind az n! Ekkor minden sorban a két permutáció inverzióinak száma együttígy A cserék számának átlaga tehát a legnagyobb érték fele, de nagyságrendben ez így is n2-es. Az elemzés eredménye az, hogy a buborékrendezés a legrosszabb és az átlagos esetben is — mindkét meghatározó művelete szerint — nagyságrendben n2-es algoritmus.

Vissza a tartalomjegyzékhez 1. A Hanoi tornyai probléma megoldásának műveletigénye A következő algoritmus, amelyet elemzünk, a Hanoi tornyai probléma megoldása.

A probléma régről ismert. Adott három rúd és az elsőn n darab, felfelé egyre csökkenő méretű korong, ahogyan az 1. A feladat az, hogy a korongokat át kell helyezni az A rúdról a B-re, a C rúd felhasználásával, oly módon, hogy egyszerre csak egy korongot szabad mozgatni és csak nála nagyobb korongra, vagy üres rúdra lehet áthelyezni.

A feladatnak több különböző megoldása van, köztük olyan iteratív heurisztikus algoritmusok, amelyek a mesterséges intelligencia területére tartoznak. Itt a szokásos rekurzív algoritmust ismertetjük. Hanoi tornyai probléma Számítógépes programok, algoritmusok esetén akkor beszélünk rekurzióról, hogyha az adott eljárás a működése során „meghívja önmagát”, vagyis a számítás egyik lépéseként önmagát hajtja végre, más bemeneti adatokkal, paraméterekkel.

Sok hasznos algoritmus rekurzív szerkezetű, és többnyire az ún. Ennek a lényege az, hogy a feladatot több részfeladatra bontjuk, amelyek egyenként az eredetihez nagyon hasonlóak, de kisebb méretűek, így könnyebben megoldhatók.

A definiált működésnek az lesz a hatása, hogy a részfeladatokat hasonlóan, további egyre kisebb és kisebb részekre osztja az eljárás, amíg el nem éri az elemei feladatok megadott méretét. A már kellően kicsi részfeladatokat közvetlen módon megoldjuk.

Logaritmus – Wikipédia

Ez az elemi lépés gyakran egészen egyszerű. Ezután a rekurzív hívások rendszerében „visszafelé” haladva minden látáskezelő eszköz összegezzük, összevonjuk a részfeladatok megoldását. Az utolsó lépésben, amikor a működés visszaér a kiinduló szintre, megkapjuk az eredeti feladat megoldását.

A módszer általános elnevezése onnan ered, hogy a rekurzió minden szintjén három alapvető lépést hajt végre: felosztja a feladatot több részfeladatra, „uralkodik” a részfeladatokon, rekurzív módon való megoldásukkal; amennyiben a feladat mérete kellően kicsiny, közvetlenül megoldja, összevonja a részfeladatok megoldását az eredeti feladat megoldásává. Ennek az általános elvnek megfelelően a Hanoi tornyai probléma rekurzív megoldási elve a következő: 1.

Algoritmusok és adatszerkezetek / Algoritmusok műveletigénye

A felső n—1 korongot helyezzük át az A rúdról a C-re a megengedett lépésekkel úgy, hogy a B rudat vesszük segítségül. Ez az eredetihez hasonló, de kisebb méretű feladat.

Az egyedül maradt alsó korongot tegyük át az A rúdról az üres B-re. Ez az elemi méretű feladat közvetlen megoldása. Vigyük át a C rúdon található n—1 korongot a B-re állandó szédülés; csökkent látás A rúd igénybe vételével, hasonlóan ahhoz, ahogyan az 1.

A rekurzív eljárás működése 1. Általános szabályként jegyezzük meg azt, hogy a rekurzióból való kijáratot „engedjük minél lejjebb”, azaz a szóban forgó változó minél kisebb értékére próbáljuk azt megadni pl.

Arra törekszünk tehát, hogy minél kisebb legyen az a részfeladat, amelyet már közvetlenül oldunk meg. Írjuk meg ezután az eljárást!

A Hanoi n,i,j,k rekurzív eljárás n számú korongot átvisz az i-edik rúdról a j-edikre, a k-adik rúd felhasználásával. Az eljárást "kívülről" a konkrét feladatnak megfelelő paraméterekkel kell meghívni, pl.

Az eljárás struktogramja a 1. A rekurzív eljárás önmagát hívja egészen addig, amíg n nagyobb nullánál. Az Átrak i,j utasítás jelöli táblázat megtekintése az 1-nél az elemi műveletet, amellyel egyetlen korongot átteszünk az i-edik rúdról a j-edikre. A Hanoi tornyai probléma megoldása Meghatározzuk az n korong átpakolásához szükséges lépésszámot.

Az algoritmus rekurzív megfogalmazása szinte kínálja az átrakások számára vonatkozó rekurzív egyenletet: Ha kiszámítjuk T n értékét néhány n-re, akkor azt sejthetjük, hogy Ezt teljes indukcióval könnyen bebizonyíthatjuk. Program a látás javítására kaptuk, hogy a Hanoi tornyai egy exponenciális műveletigényű probléma:. A legenda szerint Indiában, egy ősi város templomában a szerzetesek ezt a feladatot 64 korongra kezdték el valamikor megoldani azzal, hogy amikor a rakosgatás végére érnek, elkövetkezik a világ vége.

Ha minden korongot 1 mp alatt helyeznek át, akkor a 64 korong teljes átpakolása nagyságrendben milliárd évet venne igénybe. Ha mp-cel számolunk, ami már a számítógépek sebessége, akkor is nem egészen ezer évre lenne szükség a korongok átrendezéséhez. A nagyságrendek érzékeltetésére: az univerzumról úgy tudjuk, hogy kevesebb, mint 14 milliárd éves, a másodiknak kiszámolt időtartam pedig a homo sapiens megjelenése óta eltelt idővel egyezik meg nagyságrendben.

Kiszámítottuk két algoritmus műveletigényét a bemenő adatok méretének függvényében. Szeretnénk pontosabb matematikai fogalmakra támaszkodva beszélni az algoritmusok hatékonyságáról. Ebben a pontban ennek megalapozása történik.

Először is alkalmasan megválasztjuk az algoritmusok táblázat megtekintése az 1-nél, illetve lépésszámát jelentő függvények értelmezési tartományát és értékkészletét. A továbbiakban legyen f olyan függvény, amelyet a természetes számok halmazán értelmezünk és nem-negatív valós értékeket vesz fel:ahol.

Definiáljuk egy adott g függvény esetén azon függvények osztályait, amelyek nagyságrendben rendre Bubnovsky és látomás nagyobbak, kisebbek, nem kisebbek, nagyobbak, mint g, illetve g-vel azonos nagyságrendűek. Az osztályok jelölései és nevei: O „nagy ordó” vagy „ordó”, ”kis ordó”.