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)