NTP

1. Objasniti pojam vremenska složenost algoritma. Navesti primer.
2. Objasniti pojam prostorna složenost algoritma. Navesti primer.
3. Objasniti osnovne klase složenosti algoritama. Navesti primer za svaku klasu složenosti.
4. Poređati klase složenosti prema efikasnosti. Obrazložiti odgovor.
5. Dat je fragment koda. Odrediti vremensku i prostornu složenost i obrazložiti odgovor.
6. Navesti iskaz master teoreme. Kada se koristi master teorema? Navesti primer.
7. U kojim slučajevima se ne može iskoristiti master teorema. Navesti primere za svaki karakteristični slučaj.
8. Objasniti pojam asimptotski pozitivna funkcija. Navesti primere funkcija koje to jesu i primere funkcija koje to
   nisu.
9. Šta je uslov regularnosti? Objasniti i navesti primer.
10. Algoritam je opisan rekurentnom relacijom. Odrediti vremensku složenost algoritma primenom master teoreme.
11. Objasniti efikasan algoritam za stepenovanje brojeva. Odrediti njegovu složenost. Navesti primer.
12. Objasniti na koji način se računa vrednost polinoma u tački primenom Hornerove šeme. Odrediti složenost
    algoritma. Navesti primer.
13. Objasniti na koji način se računa vrednost broja u proizvoljnoj osnovi primenom Hornerove šeme. Odrediti
    složenost algoritma. Navesti primer.
14. Objasniti naivni algoritam za sabiranje/oduzimanje/množenje polinoma. Odrediti njegovu složenost. Navesti primer.
15. Objasniti efikasan način za ispitivanje da li je broj prost. Odrediti složenost algoritma. Navesti primer.
16. Objasniti Fermaov test primalnosti. Šta znači da je test probabilistički? Navesti primer.
17. Objasniti algoritam za generisanje prostih brojeva Eratostenovo sito. Odrediti složenost algoritma. Navesti primer.
18. Objasniti algoritam za faktorizaciju broja zasnovan na Eratostenovom situ. Odrediti složenost algoritma. Navesti
    primer.
19. Objasniti Euklidov algoritam za izračunavanje nzd dva broja. Odrediti složenost algoritma. Navesti primer.
20. Objasniti kako možemo odrediti nzs dva broja. Odrediti složenost algoritma. Navesti primer.
21. Objasniti kako možemo da odredimo nzd i nzs niza brojeva. Koja je složenost algoritma?
22. Objasniti prošireni Euklidov algoritam. Odrediti složenost. Navesti primer.
23. Objasniti pojam modularni multiplikativni inverz. Kako se može odrediti uz pomoć proširenog Euklidovog
    algoritma.