Cum de a evalua complexitatea algoritmului - conceptul de complexitatea algoritmului - conceptul algoritmului - catalog de fișiere
Analiza vitezei de executie algoritm
Există mai multe modalități de a măsura complexitatea algoritmului. Programatorii de obicei se concentrează pe viteza algoritmului, dar nu mai puțin important, și alți indicatori - cerințele pentru cantitatea de memorie, spațiu pe disc. Utilizarea algoritmului rapid nu va duce la rezultatele așteptate, în cazul în care activitatea sa va avea nevoie de mai multă memorie decât computerul are.
Memorie sau timp
Mulți algoritmi oferă posibilitatea de a alege între capacitatea de memorie și viteza. Problema poate fi rezolvată rapid prin utilizarea unei cantități mari de memorie, sau mai lent, luând mai puțin volum.
Un exemplu tipic în acest caz este cel mai scurt traseu algoritmul de căutare. Reprezentarea orașului ca o placă de rețea, este posibil să se scrie algoritmul pentru determinarea cea mai mică distanță dintre oricare două puncte ale rețelei. Nu pentru a calcula distanța ori de câte ori avem nevoie de ele, putem obține cele mai scurte distanțe între toate punctele și pentru a salva rezultatele în tabel. Atunci când avem nevoie pentru a găsi cea mai scurtă distanță între două puncte, putem lua doar departe de masa gata.
Rezultatul va fi obținut imediat, dar va necesita o cantitate mare de memorie. Harta orașului mare poate conține zeci de mii de puncte. Apoi, tabelul descris mai sus trebuie să conțină mai mult de 10 miliarde. Cells. Ie în scopul de a îmbunătăți performanța algoritmului, o suplimentare de 10 GB de memorie pentru a fi utilizate.
Din aceasta vine ideea, în funcție de complexitate volum-timp. În această abordare, algoritmul este evaluat, atât în ceea ce privește viteza de performanță, și în termeni de memorie consumate.
Problemele de olimpiada există întotdeauna o indicație a valorii maxime a timpului trece prin toate testele pentru a verifica eficacitatea algoritmului programului.
Locul ordinea de complexitate a algoritmului
Atunci când se compară diferite algoritmi, este important să se știe cum complexitatea lor depinde de cantitatea de date de intrare. Să presupunem că, dacă sortați prin procesarea de o mie de numere ia 1s și se ocupe de milioane de numere - 10s, folosind un algoritm diferit poate necesita un 2c și 5c, respectiv. În astfel de circumstanțe, este imposibil de spus sigur ce algoritm mai bun.
În general, complexitatea algoritmului poate fi estimat în ordine de mărime. Algoritmul are complexitatea O (f (n)), în cazul în care creșterea dimensiunii N. timpului de execuție de intrare crește algoritm la aceeași rată ca și funcția f (n). Luați în considerare codul care pentru matricea A [N x N] este elementul maxim în fiecare rând.
dacă A [i, j]> max atunci
În acest algoritm, o i variabilă variază de la 1 la N. La fiecare schimbare i. j variabilă este schimbată de la 1 la N. In fiecare dintre N iterații ale buclei exterioare, bucla interioară este executat de N ori, de asemenea. Numărul total de iterații buclei interioare este egală cu N x N. Aceasta definește complexitatea algoritmului O (N2).
Estimarea ordinul de complexitate al algoritmului, trebuie să utilizeze numai partea care crește cel mai rapid. Să presupunem că ciclul de lucru este descris de expresia N + 3 N. În acest caz, complexitatea este egal cu O (N 3). În calcul nu poate lua în considerare factorii constant în expresii. Algoritmul etapa de lucru 3 N 3 considerată O (N 3). Acest lucru face ca dependența O (N) din modificarea dimensiunii problemei mai evidente.
Cum de a evalua complexitatea algoritmului