| dbo:abstract
|
- A mester-tétel a egy gyakran előforduló típusának az az elemzésére szolgál. A tétel lazán fogalmazva azt mondja meg, mennyi a teljes futásideje egy olyan algoritmusnak, ami minden lépésben a-szor újra meghívja önmagát b-ed akkora bemenetre, valamint további nagyságrendű műveletet végez (ahol egy bizonyos bonyolultsági osztályba tartozik). Formálisan a mester-tétel azt mondja ki, hogy ha a T függvényt a rekurzív reláció definiálja, amiben és , akkor 1.
* , ha 2.
* , ha 3.
* , ha és valamilyen konstansra és elég nagy n-re. Az összefüggés akkor is igaz marad, ha helyett vagy áll. A tétel néhány alkalmazása:
* a minden lépésben egyszer hívja meg magát feleakkora bemenetre, és még konstans sok lépést végez; a futásideje így a rekurzív képlettel írható le, amiből a tétel alapján adódik.
* egy teljes bináris fa rekurzív bejárása során az algoritmus kétszer hívja meg magát feleakkora bemenetre, és még konstans sok lépést végez, amiből futásidő adódik.
* az is kétszer hívódik meg feleakkora bemenetre, de lépést végez mellette, a teljes futásidő így (hu)
- A mester-tétel a egy gyakran előforduló típusának az az elemzésére szolgál. A tétel lazán fogalmazva azt mondja meg, mennyi a teljes futásideje egy olyan algoritmusnak, ami minden lépésben a-szor újra meghívja önmagát b-ed akkora bemenetre, valamint további nagyságrendű műveletet végez (ahol egy bizonyos bonyolultsági osztályba tartozik). Formálisan a mester-tétel azt mondja ki, hogy ha a T függvényt a rekurzív reláció definiálja, amiben és , akkor 1.
* , ha 2.
* , ha 3.
* , ha és valamilyen konstansra és elég nagy n-re. Az összefüggés akkor is igaz marad, ha helyett vagy áll. A tétel néhány alkalmazása:
* a minden lépésben egyszer hívja meg magát feleakkora bemenetre, és még konstans sok lépést végez; a futásideje így a rekurzív képlettel írható le, amiből a tétel alapján adódik.
* egy teljes bináris fa rekurzív bejárása során az algoritmus kétszer hívja meg magát feleakkora bemenetre, és még konstans sok lépést végez, amiből futásidő adódik.
* az is kétszer hívódik meg feleakkora bemenetre, de lépést végez mellette, a teljes futásidő így (hu)
|
