Eficiența algoritmică

Dublaj vocal: Am primit acum o veste că vor trimite un nou rover pe Marte. Noi suntem responsabili de un lucru și anume de a programa algoritmul roverului care verifică dacă un număr e prim. Să presupunem că roverul comunică folosind RSA. Are nevoie de un algoritm care poate rula un test de primalitate. Când proiectezi un rover sau orice altceva care merge în spațiu, trebuie să fii foarte eficient din orice punct de vedere. Piesele folosite trebuie să fie foarte ușoare. Cantitatea de putere folosită de toate subsistemele trebuie să fie minimă. Trebuie să salvezi energie și greutate în toate etapele din procesul de proiectare. Vom avea o muncă grea de făcut. Trebuie să lucrăm inclusiv cu numere atât de mari. Trebuie să se întâmple foarte repede. Dacă îi dăm un număr foarte mic, de exemplu 90, ar trebui să calculăm aproape la fel de repede ca în cazul acestui mare număr. Pe măsură ce mărim dimensiunea problemei, nu vrem să observăm nicio încetinire notabilă. Vreau să analizăm întrebările sau ideile utilizatorilor sau ideile utilizatorilor care sunt foarte bune din punct de vedere matematic. Verificăm dacă N este prim sau compus. Pentru un număr N, să ne gândim la spațiul tuturor posibilităților. Dacă N este 100, spațiul e de la 2 la 100. Algoritmul nostru explorează acest spațiu. Imaginează-ți un algoritm explorând un spațiu. La fiecare moment întreabă- Privește-l ca pe un pas, un pas simplu. Algoritmul pune o întrebare și de fapt, întrebarea este un test de primalitate. Să presupunem că acesta e un număr A, ne-am întreba în testul de divizibilitate: "este N divizibil cu A?" Hai să încercăm, îl punem pe A aici și încercăm "N împărțit la A" și ne uităm dacă restul este 0, ceea ce înseamnă că A este un divizor al lui N, vom spune că "Ah, știm 100% că acest număr este unul compus". Altfel, la fiecare pas, nu vom fi siguri deloc. Ar putea fi prim dar nu știm cu siguranță. Continuăm căutarea până ajungem la final. Amintește-ți că momentul crucial în acest caz era la rădăcina pătrată a lui N. Cel mai rău caz este atunci când N este prim, căutăm până la rădăcina pătrată a lui N și atunci putem spune "Ah, este prim și suntem 100% siguri". În cazul în care N este multiplul a două numere prime, de 7 ori 7 egal 49 dacă trecem 49 prin algoritmul nostru, se întâmplă cel mai rău caz. Ajungem chiar până la rădăcina pătrată a lui N. Primul set de întrebări, de exemplu APatraDimensiune întreabă "Odată ce eliminăm 2 ca nefiind compus, atunci toți multiplii lui 2 ar putea fi scoși din calcul, la fel pentru 3, 4, 5 et cetera". Este o observație foarte bună. Algoritmul nostru vechi înainta cu câte 1 la fiecare pas. Putem utiliza proprietăți pe care le știm despre numere compuse, precum că știm sigur că dacă un număr e divizibil cu 2, atunci e un număr compus (dacă e mai mare decât 2, căci 2 este prim). Atunci putem spune că 4 este număr compus. Am sărit peste 5, îmi pare rău. Patru, șase, opt, zece și deci în schimb putem înainta astfel. Trei, cinci, șapte, nouă. O categorie de întrebări care încearcă toate să reducă spațiul căutării. Dacă eliminăm toate numerele pare, spațiul de căutare s-a redus de la rădăcina pătrată a lui N la rădăcina pătrată a lui N împărțit la 2. Putem găsi și alte strategii pentru numere compuse ca să facem spațiul de căutare chiar mai mic. Celălalt tip de întrebări sunt legate de cazul când găsim un divizor. Adică atunci când găsim un număr A care ne permite să spunem "Oh, știm acum că N este număr compus". Lola spune "Nu am putea reduce timpul dacă ieșim din buclă de îndată ce verificăPrim este fals?" Da, este total corect și este un lucru pe care dorim să îl facem. Imediat ce găsim un divizor pe măsură ce căutăm folosind un increment definit de strategia de căutare pe care o folosim. Asta înseamnă că numărul trece testul nostru și putem spune cu siguranță că putem opri algoritmul prematur. Ne oprim și afirmăm că "Am terminat. Nu vom continua căutarea". Oprirea prematură e foarte bună doar că nu ne ajută în cazul cel mai complex, adică atunci când N este prim, oprirea prematură nu ne va ajuta acolo. Putem vizualiza cum aceste îmbunătățiri ne ajută să reducem spațiul căutării și deci prevenind atât de multe căutări care au loc înăuntrul calculatorului și care, depinzând de calculator, vor reduce durata de timp necesară. Acum îți pot arăta simularea pe care am pregătit-o și care ne ajută să comparăm doi algoritmi pe baza a câți pași au loc în timpul execuției. În partea stânga este algoritmul A, care e diviziunea de probă și care verifică de la 2 până la rădăcina pătrată a lui N. În dreapta este algoritmul B, care este algoritmul nostru îmbunătățit. În acest caz, am aplicat verificarea dacă numărul e divizibil cu 2 astfel încât să facem doar jumătate din pași. De asemenea voi încheia prematur în acest algoritm B. Nu e perfect, doar am aplicat doar câteva modificări de la utilizatori ca să vedem ce se întâmplă. Acum mă voi juca puțin cu câteva setări de aici ca să îți arăt. Aici, pe măsură ce glisez, putem vedea algoritmul A. Avem rezultatul, dacă numărul este compus sau prim. Jos de tot putem vedea numărul de pași. Primul lucru de observat este pe partea dreaptă, că, la fiecare două numere, e nevoie de doar un pas. Știm de ce se întâmplă asta. Dacă este un număr par precum acesta, atunci va opri execuția. Algoritmul nostru vechi necesita 314 de pași. Noul nostru algoritm a avut nevoie de doar un pas deoarece verifică dacă este divizibil cu 2. Pare o optimizare foarte bună. Totuși, pe măsură ce construim datele de intrare, vei vedea că pașii cresc și că bara crește și devine roșie când ne apropiem de zona unde vom intra în colaps. Linia roșie de sus este limita de pași. Dacă bara atinge aici, vom eșua, ceea ce înseamnă că roverul nostru se va strica. Aici, este navigatorul web care se va strica de fapt. O să mă apropii de linia roșie. Sunt aproape de linie acum și rulează foarte încet. Pot să simt că navigatorul meu e aproape de a se strica și să îmi dea un mesaj de eroare. Observă că algoritmul îmbunătățit a avut nevoie de doar doi pași, în acel caz, dar nu uita și de cel mai rău caz. Așa că voi schimba- Am aici câteva numere prime foarte mari salvate ca exemplu. Trebuie să putem gestiona orice caz. Nu știm cu ce va avea nevoie algoritmul nostru să se confrunte. Dacă îi trimit un număr prim foarte mare, uitați ce se întâmplă. Algoritmul B, după cum știm face jumătate din pași în cel mai rău caz, dar aici tot face mulți pași pentru că este cel mai rău caz. Ne apropiem de impact aici, iar acest nu este un număr prim chiar foarte lung. Suntem tot sub 15 cifre. Și când pun acest număr de 12 cifre în algoritmul nostru, să vedem ce se întâmplă. Merge foarte greu, e pe cale să crape. Uite, ambii algoritmi au depășit cu mult limita. Nu a funcționat. Algoritmul nostru îmbunătățit nu este încă suficient de bun. Dar acum avem o privire de ansamblu a ce trebuie să îmbunătățim, care este numărul de pași în cel mai rău caz. Avem și acest instrument foarte util care ne arată cât de mult crește, cât de repede crește numărul de pași cu cât numărul de intrare devine mai mare. În continuare voi explica cum am configurat asta ca să îți poți seta algoritmul și să îl compari cu cazul de bază și să vezi cât de bun îl poți face.