$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \newcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Tagovi: algoritam; slozenost

Uvod u algoritme / Složenost algoritama

Složenost algoritama

  • Dozvoljeno polaganje
  • Osnovni++
  • Nema
  • Andreja Ilić
  • 8/4/2013
  • algoritam; slozenost

Analiza algoritma predstavlja postupak kojim se predviđa ponаšanje i vrši procena potrebnih resursa algoritma. Tačno ponašanje algoritma je nemoguće predvideti, zato se za njegovu analizu razmatraju samo glavne karakteristike, a zanemaruju neki manji faktorisa kojima ćemo se kasnije upoznati. Osnovni metod koji se pri tome koristi je aproksimacija. Na ovaj način se, iz skupa mogućih algoritama za rešavanje nekog konkretnog problema, može izdvojiti najefikasniji (ili klasa efikasnih algoritama). U ovoj lekciji ćemo razmatrati vremensku složenost algoritma – memorijski zahtevi će biti pomenuti samo ako nisu u nekim "normalnim" granicama.

Slika 1.Strip o složenosti problema putujućeg trgovca

Većina učenika, neretko i studenata, nije upoznata sa ovim pojmom i njegovom važnošću. Često u toku ispita / takmičenja dobijamo pitanja vezana za ograničenja ulaznih podataka, jer većina takmičara ne razume zašto su ona bitna. Ideja ovog dokumenta je da takmičarima približi ovaj pojam i njegovu značajnost. U mnogim knjigama ovoj priči nije posvećeno dovoljno pažnje. Neretko se ovaj pojam uvodi jako formalno što predstavlja problem čitaocu da razume njegovu suštinu. Akcenat u ovoj lekciji će biti na razmatranju i analizi konkretnih problema. Razni primeri koje ćemo analizirati će vam pomoći da uočite razlike između algoritama koji rešavaju isti problem.