Masteryhtälöjä

Masteryhtälöitä, eli mestariyhtälöitä, käytetään tietotekniikassa ja algoritmiikassa analysoimaan rekursiivisten algoritmien aikakompleksisuutta. Ne tarjoavat systemaattisen tavan määrittää suorituskyvyn kasvu suhteessa syötteen kokoon. Yleisessä muodossaan masteryhtälö on T(n) = aT(n/b) + f(n), missä T(n) on rekursiivisen funktion suoritusaika syötteelle kokoa n, a on rekursion määrä, n/b on syötteen koko rekursiivisissa kutsuissa, ja f(n) on aika, joka kuluu jakamis- ja yhdistämisvaiheisiin.

Masteryhtälön ratkaisemiseksi on olemassa kolme pääasiallista tapausta, jotka riippuvat f(n):n suhteesta n^(log_b a):in. Ensimmäisessä tapauksessa, jos f(n) kasvaa asymptoottisesti hitaammin kuin n^(log_b a), ratkaisu on O(n^(log_b a)). Toisessa tapauksessa, jos f(n) on asymptoottisesti samaa suuruusluokkaa kuin n^(log_b a), ratkaisu on O(n^(log_b a) * log n). Kolmannessa tapauksessa, jos f(n) kasvaa asymptoottisesti nopeammin kuin n^(log_b a) ja tietyt regulariteettiehdot täyttyvät, ratkaisu on O(f(n)).

Masteryhtälöä voidaan soveltaa moniin yleisiin algoritmeihin, kuten yhdistämisjärjestykseen (merge sort) ja pikajärjestykseen (quick sort). Se yksinkertaistaa huomattavasti rekursiivisten algoritmien monimutkaisuusanalyysiä verrattuna esimerkiksi rekursiopuiden piirtämiseen. Yhtälö on hyödyllinen työkalu algoritmien suunnittelussa ja tehokkuuden arvioinnissa.