| 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)
|
| rdfs:comment
|
- 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. A tétel néhány alkalmazása: (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. A tétel néhány alkalmazása: (hu)
|
