Algoritmai špera


Rusavimo. Optimalaus kelio radimo algoritmas. Kraskalo metodas.

Informatikos Špera. Posąrašio dydžio nustatymo metodas. Idealus masyvo dydis. Balansavimas arba skaidymo i lygias dalis principas. Binarinis įterpimo algoritmas. Rūšiavimas išrinkimu. Binarinai paieskos medziai. Nuosekli paieška paprastame masyve. Principas - ‘skaldyk ir valdyk’. Balansavimas arba skaidymo i lygias dalis principas. Rekurentinių lygčių sprendimas. Rusavimo algoritmai. Rūšiavimas lyginant elementus. Rūšiavimas piramide. Prioritetu eiles. Rūšiavimas suskaldymu (quick sort). Ekspermentinis statistinis algoritmų tyrimas. Dviejų algoritmų darbo ekspermentinis statistinis palyginimas. Optimalus rūšiavimas (pagal minimalų palyginimų sk. , reikalingą surūšiuoti n elementų. Maksimalaus elemento išrinkimas iš n elementų sekos. Dviejų didžiausių elementų radimas. Geriausio (max) ir blogiausio (min) elemento išrinkimas. K-ojo didesnio elem. Išrinkimas[be rūšiavimo]. Veiksmai su aibemis(ds požiūriu). Kraskalo alogoritmas. Optimalūs binarinės paieškos medžiai. Paskirstymo metodas. Operacijų apjungti ir rasti atlikimo algoritmai. Medžio tipo struktūros. Dinaminis programavimas. Kai kurių dinaminio programavimo uždavinių formulavimai. Godūs algoritmai. Hufmano kodai. Paieška į gylį grafuose. Stipriai susijusių komponenčių išskyrimas orientuotame grafe. Grafų susietumo matrica. Trumpiausio kelio radimas.


Pvz. Turime masyva, kreipimasis į masyvą paprastai užima tam tikrą pastovų laiką. Kai reikia surasti reikiamą įrašą, reikia perbėgti nuosekliai masyvą.Įrašai gali būti išdėstyti atvirkštine tvarka arba jie būna sutvarkyti. Nuosekliai ieškan įrašų rekia peržiūrėti nuosekliai juos visus. Vid.peržiūrėų įrašų sk. ieškant yra Lap =L/2.

Jeigu išdėstyti atsitiktine tvarka, tai mums reikės perbėgti pusė sąrašo, jei įrašo nėra reikės pereiti visą sąrašą. Lapn =L.

Else if a=A[L(f+l)/2] then return ‘Taip’ else if a

( n/2i ((1; i((log2 n(. f(n)((log2n(+1 arba f(n) ( (log2 (n+1)( .

Panagrinesime vidutinis palyginomu skaicius. Surasti irasa binarineje paieskoje. Ieskomas irasas yra kokioje tai sekoje.

f(n)(1* 1/n + 2*2/n + 3*4/n +...+ ((log2 n( + 1)*2(log n( /n ( 1/n * (i(1(log n(+1 (i * 2i-1).

T(n)= {0, kai n-1; 1, kai n=2, T((n/2() + T ((n/2()+2, kai n >2 . Algoritmas yra toks:

Šio algoritmo sudėtingumas (( n log2 n).

Realiai n gali buti bet koks tada suskaidoma seka į (n/2( ir (n/2(rekurentine lygtis bus tokia:

SAVE yra papildomas masyvas tai sio metodo trukumas nes reikia papildomo masyvo. Skaidymas I lygias dalis turi ir isimciu.

T(c2) ( aT(c) + bc2 ( a(ab + bc) + bc2 ( a2b + abc + bc2 ( bc2(1+ a/c + a2/c2) ......

Jei a > c didejanti geometrine progresija T(n) = bn* (1-(a-c) logcn *a/c) / 1-a/c; ((n (a/n) logcn ) = (( n 1 + logca/c );

T Apie rekurentinės lygties tipo T(n)=aT(n\c)+f(n), kur a≥1, c≥1, f(n)-teigiama f-ja. 1) Jei f(n)= ((n(lo gc a) - () ,tai T(n)= ((nlogc a). 2) Jei f(n)= ((nlogca) ,tai T(n)= ((nlog c a . log n. 3) Jei f(n)= ((n(log c a) + () ,tai T(n)= ((f(n)), jei af(n\c)≤bf(n) (b>1 dideliems n).

A1 A2 ... An - K- maciai kortezai (A i sudarytas is kazkiek simboliu a1,a 2, a3 .. an ) rusiuojama pirmiausia pagal paskutine k-taja komponente. Po to pries paskutine k – 1 komponente ir taip toliau, kai isrusiuosim pagal 1 maja komponente tai seka bus isrusiuota. Realizimu surasome visu kortezus i bendra eile, sukuriame m pagalbiniu eiliu Q(i), kur i = 0.1...m-1. Analizuojant korteza pagal atitinkama komponente, jis tapatinamas i atitinkama pagalbine eile. Taip daroma tol kol pagrindine eile istusteja po to pagalbines eiles suduriamos i pagrindine eile Q(0), Q(1)..Q(m-1).

Algoritmas: begim patalpinti A1, A2..An i eile EILE;

Begin for l ( 0 until m – 1 do padaryti eiles Q[l] tuscios: while eile EILE netuscia do

Begin tegul Ai – pirmos elementai eileje EILE; patalpinit Ai is EILE i Q[a i j ] end;

Prijungti Q[l] turini i eiles EILE gala end end;

Aalgortimo sudetingumas (( n+m) k ) skaiciavimo laikas proporcingas elementu skaiciui ir galimu simboliu skaiciui. Tiesinio sudetingumo algoritmas, sis algoritmas netinka kai n mazas. b.Nevienodo ilgio kortežų rūšiavimas

Padaryti sarasa Q[j] tuscia end end end; algoritmo sudetingumas ([ Lmax m + l*] tiesinis l* = (= 1l max n i laikas perkeltu kortezu;

Buble sort For neisrusiuotas from upper downto lower + 1

Cia gali buti naudojamas skaitliukas kuris skaiciuoja sukeitimu skaiciu, jeigu atlikus iteracija sukeitmu nebuvo padaryta, tai tas rodo kad masyvas surusiuotas

Virutinis pakeitimu skaicius: Jeigu seka jau isrusiuota tai pakeitumu skaicius bus lygus 0. jei max palyginimu skaicius bus ju seka isrusiuota atvirksciai (0 + n(n-1)/2 ) / 2 = n(n-1) /4;

  • Informatika Šperos
  • 2010 m.
  • 3 puslapiai (10745 žodžiai)
  • Informatikos šperos
  • Microsoft Word 99 KB
  • Algoritmai špera
    8 - 2 balsai (-ų)
Algoritmai špera. (2010 m. Kovo 03 d.). http://www.mokslobaze.lt/algoritmai-spera.html Peržiūrėta 2016 m. Gruodžio 06 d. 03:00