Numărul de operații pentru algoritmi de complexitate diferită
Complexitatea asimptotică a algoritmului este o metodă de estimare a complexității computaționale a algoritmului "până la o constantă" aplicată în teoria complexității. De obicei, scrisă în notația "big O".
Acesta este utilizat pe scară largă ca o evaluare corectă a complexității în ceea ce privește operațiunile elementare sunt adesea complexe (inclusiv, de asemenea, depinde de ceea ce este necesar pentru operația elementară - o acțiune într-un anumit limbaj de programare, ceasul CPU) și nu are nici un sens pentru volume mari de date de intrare, atunci când părțile în continuă creștere a funcției temporare încetează efectiv să afecteze cantitatea totală de muncă efectuată.
Cea mai frecvent folosită estimare asimptotică a timpului de operare al algoritmului este de la început, scrisă ca O (f (n)), unde n este volumul datelor de intrare. Dacă acceptăm funcția de rulare a algoritmului în funcție de volumul de date de intrare ca F (n), atunci putem spune că pornind de la un anumit număr N pentru toate n> N inegalitatea | F (n) | <= |N*f(n)|. иными словами, с некоторого момента функция F(n) растет не быстрее. чем N*f(n), где N — константа.
Estimări ale complexității algoritmilor:
- Complexitatea logaritmică - depinde de datele de intrare ale lui n ca N * log (n), în special, complexitatea acestei operații este căutarea într-o matrice indexată, ridicând rapid la o putere arbitrară. În practică, complexitatea lui N * n * log (n) este întâlnită mai des.
- Complexitatea polinomului depinde de datele de intrare ale n ca N * n ^ c, unde c este un anumit grad. Numai gradul cel mai înalt al polinomului este indicat, deoarece cu n mai mic, gradele mai mici încetează să influențeze în mod semnificativ. De exemplu, căutarea dublă a matricei are complexitatea O (n2), implementarea metodei Schulze pentru n candidați este O (n ³).
- Complexitatea exponențială - depinde de datele de intrare n ca N * e ^ n. Utilizarea algoritmilor cu o astfel de complexitate este evitată, sunt sarcini complicate pe grafice, operații complicate de căutare în mai multe tabele în MySQL și așa mai departe.
Este de asemenea posibilă o complexitate mai mare, de exemplu, N * n.
Articole similare
Trimiteți-le prietenilor: