imagine de la google

când trebuie să rezolvăm o problemă și când sunt disponibile mai multe moduri de a rezolva acea problemă (de exemplu, problema multiplicării lanțului matricei), la acel moment este necesară analiza algoritmului.

analiza algoritmilor înseamnă estimarea complexității lor într-un sens asimptotic. Termenul” analiza algoritmilor ” a fost inventat de Donald Knuth. Analiza algoritmilor este determinarea cantității de resurse de timp și spațiu necesare pentru executarea acesteia.

majoritatea algoritmilor sunt de natură recursivă, folosesc strategia divide and conquer. Algoritmul recursiv se numește pentru celelalte intrări. Aceasta este de obicei o parte din intrarea originală, dar are o dimensiune mai mică (sub-problemă). Există multe modalități de a rezolva relația de recurență. Acestea sunt următoarele:

1. Teorema maestrului

2. Metoda arborelui recurenței

3. Metoda de substituție

4. Schimbarea metodei variabile

dintre toate aceste metode, teorema master este cea mai rapidă metodă de a găsi complexitatea în timp a funcției. Este foarte ușor de înțeles și ușor de aplicat. Trebuie doar să ne amintim unele cazuri. Deci, aici vom merge.