Ridicarea la putere in timp logaritmic
2Probabil au fost cateva persoane ce nu au inteles la un moment dat rezolvarea problemei Ucif in O(1) explicata de Alex si Andrei Misarca si au dorit sa inteleaga ce a facut Cosmina in prezentarea problemei.Astfel noi vom incerca sa ne jucam cu problema de mai sus dar folosind o metoda de rezolvare nu tocmai optima in cazul problemei respective , ci doar o vom folosi pentru a avea un exemplu pe care sa ne bazam.
Ne vom axa doar pe determinarea ultimei cifrei a lui x^x.Metoda clasica de rezolvare presupune ridicarea la putere in timp liniar.:
int ucif(int x,int n,int modul) { if(n==0) return 1; int cif = 1; while(n--) { cif = (cif*x)%modul; } return cif; } // Modalitate de apelare: printf("%d",ucif(9,9,10));
Din fericire,aceasta solutie va obtine punctajul maxim daca nu ma insel pe testele la problema respectiva,insa cu marirea lui n se va simti o diferenta enorma in timpul de executie, datorita complexitatii acestuia(n^2).
Pentru asta va trebui sa ne folosim de ridicarea in timp logaritmic, o rezolvare ce va imbunatati mult timpul de executie al algoritmului.
int ucif(int x,int n,int modul) { int cif = 1; int a; if(n==0) return 1; a = x; for (int i = 0; (1<<i ) < = n; i++) // Luam toti biti lui p la rand { if ( ((1<<i) & n) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie cif= (cif * a) % modul; a=(a * a) % modul; // Inmultim a cu a ca sa obtinem n^(2^(i+1)) } return cif; } // Modalitate de apelare: printf("%d",ucif(9,9,10));
In cazul in care doriti o rezolvare recursiva , puteti alege rezolvarea Cosminei de la problema Ucif , cu cateva modificari sa o facem in stilul celor de mai sus(cea de mai jos) :
int ucif(int x, int n,int modul) { int tip; if(n==0) return 1; if(n%2==1) return (x*ucif(x,n-1,modul))%modul; tip=ucif(x,n/2,modul)%modul; return tip*tip%modul; }
Puteti citi mai multe detalii de fundamentul matematic al acestui algoritm pe wikipedia.
„daca vom mari limitele lui n, sa spunem cateva zeci de mii, atunci timpul liniar va duce la o solutie in timp patratic ceea ce este groaznic.” …
Cum adica pt n foarte mare complexitatea devine din O(n) in O(n^2) ? Mi se pare o aberatie fraza asta, complexitatea unui algoritm este acceasi pentru orice n… ori e O(n) ori O(n^2) … nu pot sa fie ambele in acelasi timp >.<
Imi cer scuze pentru ambiguitate,am reformulat acea fraza.Ideea era ca la un n suficient de mic este insesizabila acel ordin n^2.Cu cat se apropie de n=1000 si il depaseste cu atat impactul asupra timpului este mai criminal. 😀