Ce întrebare este un astfel de răspuns. )
Se estimează numărul de acțiuni. Acest lucru duce adesea la unele relații recurente, care într-o anumită măsură, este dificil de rezolvat - deși există soluții globale gata făcute, atât de mulți algoritmi pentru a estima nu este atât de dificil.
Cu toate acestea, trebuie să ținem cont de faptul că atunci când se evaluează complexitatea algoritmului ar trebui să fie luate în considerare structurile de date utilizate - de exemplu, algoritmul lui Dijkstra, mult depinde de modul în care coada de prioritate pusă în aplicare, și într-adevăr în algoritmi grafic, depinde foarte mult de reprezentare grafic - liste sau matricea de adiacență.
Ca un exemplu simplu - multiplicarea uzuală a matricelor nxn - fiecare element al matricei noi este obținut prin înmulțirea și însumarea produselor elementelor rândului și coloanei corespunzătoare. Lungimea rândului / coloanei este n. operații O (n) totale pentru a calcula un element al matricei rezultate. În total, există n 2, complexitatea algoritmului este O (n 3).
Postat pe 19 februarie, la 7:29 am
Precum și din alte estimări „dezinvolt“ (bazată pe intuiție), sunt deja în procesul de învățare: în disponibilitatea de blocuri pe care le poate funcționa în mod inconștient în domeniul ales, datorită practicii scop.
Nici măcar nu știți cum este implementat în mod specific ceva. De exemplu, dacă algoritmul la un anumit pas necesită sortarea datelor aleatoare, este rezonabil să presupunem O (n log n) pentru algoritmul bazat pe comparație, indiferent de implementarea particulară. Sau atunci când se uită la masă în baza de date, în cazul în care liniile de mult (atunci când un mare O este semnificativă de a vorbi), ne putem aștepta ca indicele va crea implementare de bună calitate (căutare de O (n) O (log n) se aprinde). În caz de îndoială, puteți măsura.
Pentru a găsi sau a testa un răspuns intuitiv, puteți formula expresii de recurs sau sumele parțiale pe care să le construiți, folosind calculatorul pentru a calcula. Deoarece există O (c * n) == O (n) și O (n * n + n) == O (n * n), iar cealaltă pentru a simplifica conversia, mulți algoritmi pot fi reduse la un număr mic de cazuri de bază. Procesul necesită atenție, dar este destul de clar (mai ales dacă folosiți ceva asemănător cu Wolfram, Max, Simpia). Cum de a găsi complexitatea timpului unui algoritm.
În consecință, există cazuri când eforturile concentrate, folosind abordări evidente, nu dau un rezultat, atunci merită să vă opriți puțin timp, să treceți la alte sarcini. Iluminarea poate veni în momentul cel mai neașteptat (dar este deja în afara casetei).
Uită-te la ce algoritmi sunt utilizați în sarcinile care vă interesează. Noi algoritmi cu o mai mare complexitate nu apar în fiecare zi.
Începeți cu cel mai simplu cod în limbajul și cadrul dvs. și aflați complexitatea acestuia (de exemplu, "ștergerea unui element dintr-un matrice de către un index"). Cunoscând complexitatea construcțiilor elementare, găsiți complexitatea blocurilor de cod (compuse din aceste construcții) pe care le întâlniți adesea.
Este posibil în direcția opusă: pentru a începe cu un cod de nivel înalt și coboară treptat, niveluri mai scăzute de abstractizare ca la blocuri cunoscute ajunge la tine (adăugarea de numere fixe, care sunt mașină de cuvânt a vizitat :. O (1) În cazul în care un număr arbitrar n ia O (log n) este proporțională cu numărul de biți din număr. Vedeți tabelul dificultăților în timp.
Practicați până când majoritatea codului de zi cu zi nu vă puteți dezlege.
Trimiteți-le prietenilor: