Algoritmi i kompleksnost
25 Questions
1 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Koje od navedenih akcija se mogu izvesti na podaćnim strukturama?

  • Pretraživanje (correct)
  • Kompilacija
  • Deklaracija
  • Izvršavanje

Svaka jednostavna operacija na Random Access Machine se izvodi u tri vremenske jedinice.

False (B)

Šta predstavlja T(n) u kontekstu brojenja operacija?

T(n) predstavlja funkciju koja daje broj izvršenih operacija u zavisnosti od broja ulaznih podataka.

Algoritam B je __________ od algoritma A.

<p>brži</p> Signup and view all the answers

Uparite akcije sa njihovim opisima:

<p>Pretraživanje = Profinding specific data in a structure Sortiranje = Arranging data in a specified order Umetanje = Adding data to a structure Brisanje = Removing data from a structure</p> Signup and view all the answers

Koje od sljedećih karakteristika opisuje algoritam?

<p>Postupak za rješavanje problema (A)</p> Signup and view all the answers

Algoritmi ne moraju imati konačan broj koraka.

<p>False (B)</p> Signup and view all the answers

Šta predstavlja ulaz u algoritmu?

<p>Podaci koji se unose u algoritam radi obrade.</p> Signup and view all the answers

Algoritam se može opisati putem ________ ili programskog jezika.

<p>psевdoјезика</p> Signup and view all the answers

Uparite sljedeće pojmove sa njihovim opisima:

<p>Ulazni podaci = Podaci koji se obrađuju u algoritmu Izlazni podaci = Rezultat obrade ulaznih podataka Koraci algoritma = Postupci koji se izvršavaju radi rješavanja problema Procedura = Jasno definisan niz operacija ili instrukcija</p> Signup and view all the answers

Koji od sledećih članova se uklanja kada se određuje složenost algoritma uz oznaku O(..)?

<p>Svi članovi osim člana sa najvišim stepenom (B)</p> Signup and view all the answers

Složenost algoritma uvek zavisi samo od broja operacija koje se izvršavaju unutar petlji.

<p>False (B)</p> Signup and view all the answers

Šta predstavljaju O(n), O(n^2) i O(log n) u kontekstu algoritama?

<p>Asimptotska složenost algoritama.</p> Signup and view all the answers

Složenost algoritma __________ se analizira na osnovu vremena potrebnog za izvršavanje svake njegove operacije.

<p>rekurzije</p> Signup and view all the answers

Uskladite različite formule složenosti sa odgovarajućim opisima:

<p>O(1) = Konstantno vreme izvršavanja O(n) = Linearno vreme izvršavanja O(n^2) = Kvadratno vreme izvršavanja O(log n) = Logaritamsko vreme izvršavanja</p> Signup and view all the answers

Koji izraz najbolje opisuje složenost petlji koji iterira od 0 do n?

<p>O(n) (D)</p> Signup and view all the answers

Koji je najgori slučaj vremena izvršavanja rekurzivnog algoritma za faktorijal?

<p>O(n)</p> Signup and view all the answers

Koja od sledećih opcija najbolje opisuje funkciju T(n)?

<p>Funkcija koja opisuje stvarno vreme izvršavanja algoritma. (B)</p> Signup and view all the answers

Gornja asimptotska granica je predstavljena kao O(g(n)).

<p>True (A)</p> Signup and view all the answers

Šta je 'Gole O' u kontekstu analize algoritama?

<p>Metod za procenu složenosti algoritma i gornja asimptotska granica.</p> Signup and view all the answers

U formuli T(n) je O(g(n)) postoje pozitivne konstante c i _______ takve da T(n) < c g(n) za n > n0.

<p>n0</p> Signup and view all the answers

Upoznajte sledeće termine sa njihovim definicijama:

<p>T(n) = Vreme izvršavanja algoritma g(n) = Gornja granica T(n) n = Broj ulaznih podataka O(g(n)) = Asimptotska notacija</p> Signup and view all the answers

Koja od sledećih tvrdnji je tačna o algoritmima A i B?

<p>Algoritam A je bolji ako je TA(n) = 0. (B)</p> Signup and view all the answers

Za veoma velika n, ne možemo odrediti koji je algoritam brži bez dodatne analize.

<p>True (A)</p> Signup and view all the answers

Koja je svrha korišćenja 'Gole O' notacije?

<p>Da se pojednostavi procena složenosti algoritma i eliminišu nepotrebne detalje.</p> Signup and view all the answers

Flashcards

Алгоритам

Процедурата за решавање на даден проблем, која се претставува како низа од чекори, спроведени во конечен број пати.

Сложеност на алгоритмот

Опишува колку ресурси (време или меморија) се потребни за извршување на алгоритмот, во зависност од големината на влезот.

Податочни структури

Податочни структури се начини на организирање и складирање на податоци, за да се овозможи ефикасен пристап и манипулација со нив.

Опис на алгоритмите

Описот на алгоритмот се дава преку јазик кој е лесно разбиралив од луѓето, но е доволно прецизен за да се имплементира во компјутерски програм.

Signup and view all the flashcards

Аретипи на алгоритми

Различни видови на алгоритми кои се користат за решавање на конкретни проблеми.

Signup and view all the flashcards

Што се податочни структури?

Податочните структури се начини на организирање и чување на информациите кои треба да бидат обработени од страна на програмата.

Signup and view all the flashcards

Зошто е важен изборот на податочна структура?

Изборот на соодветна податочна структура влијае на ефикасноста на алгоритмите кои ја користат.

Signup and view all the flashcards

Како се манипулираат податочни структури?

Постојат многу операции кои може да се извршат врз податочните структури, како што се пребарување, вметнување, бришење, сортирање итн.

Signup and view all the flashcards

Што е Random Access Machine (RAM)?

Random Access Machine (RAM) е хипотетички компјутер кој се користи за евалуација на перформансите на алгоритмите.

Signup and view all the flashcards

Што е временска комплексност?

Времеската комплексност на алгоритмот се мери преку бројот на чекори кои алгоритмот ги извршува во зависност од големината на влезот.

Signup and view all the flashcards

Veličina problema (n)

Mjera za veličinu problema, predstavlja broj ulaznih podataka koje algoritam obrađuje.

Signup and view all the flashcards

Funkcija složenosti (T(n))

Funkcija koja opisuje broj operacija koje algoritam izvršava u zavisnosti od veličine problema (n).

Signup and view all the flashcards

Asimptotska složenost

Sposobnost procjene složenosti algoritma bez detaljnog brojanja svih koraka, koristeći aproksimacije i gornje granice.

Signup and view all the flashcards

Notacija "Veliko O" (Big O)

Formalna metoda za procjenu gornje granice za funkciju složenosti algoritma.

Signup and view all the flashcards

Poređenje složenosti algoritma

Za dva algoritma, A i B, ako je T(n) za algoritam A manje od T(n) za algoritam B za sve n veće od nekog n0, tada je algoritam A brži.

Signup and view all the flashcards

Gornja granica funkcije složenosti (g(n))

Funkcija koja opisuje gornju granicu za funkciju složenosti algoritma. Kako n raste, T(n) će uvijek biti manja ili jednaka g(n).

Signup and view all the flashcards

Formalna definicija "Velikog O"

Postoji pozitivna konstanta c i broj n0 tako da za sve n veće od n0, T(n) će biti manja od c pomnoženo sa g(n).

Signup and view all the flashcards

Ponašanje T(n) u odnosu na g(n)

Kako n raste, T(n) će se ponašati kao g(n) u smislu rasta, ali može biti i manja. Funkcija g(n) daje približnu procjenu za složenost algoritma.

Signup and view all the flashcards

Ознака O(g(n))

Оваа ознака се користи за да се определи комплексноста на алгоритмите. О(g(n)) се зема САМО членот со најголемиот степен на асимптотската функција g(n). На пример, O(n + n log n + n^2) е еднакво на O(n^2).

Signup and view all the flashcards

Правила за користење на ознаката O

При користење на ознаката O, се отстрануваат сите членови освен членот со највисок степен. Константите се отстрануваат бидејќи не влијаат на брзината на раст кога n оди во бесконечност.

Signup and view all the flashcards

RAM модел

Овој модел се користи за да се анализира времето на извршување на алгоритмите. Времето на извршување може да се подели на најдобро време, средно време и најлошо време. Големо О се користи за да се оцeни времето на извршување во најлош случај.

Signup and view all the flashcards

Комплексност на циклус

Ова се операциите кои се извршуваат во циклус. Времето потребно за нивно извршување се множи со бројот на итерации на циклусот. На пример, ако циклус се извршува n пати и секоја итерација трае 2 единици време, тогаш комплексноста на циклусот е O(n).

Signup and view all the flashcards

Комплексност на вгнезден циклус

Вгнездените циклуси се циклуси внатре во други циклуси. Времето потребно за нивно извршување се множи со производот од бројот на итерации на секој циклус. На пример, if the outer loop iterates n times and the inner loop iterates m times, then the complexity of the nested loop is O(n*m).

Signup and view all the flashcards

Комплексност на последователни кодови

Кај последователни извршувања се зема најголемата кардиналност од блоковите на последователни кодови. На пример, ако еден блок е O(n) и друг е O(n^2), тогаш комплексноста на алгоритмот е O(n^2).

Signup and view all the flashcards

Комплексност на IF/ELSE

Комплексноста на IF/ELSE структури се одредува со збирот на времето потребно за проверка на условот и подолгото време од двата блока кодови (тоа што е во IF или ELSE).

Signup and view all the flashcards

Study Notes

Predmet: Algoritmi i kompleksnost

  • Predmet se bavi algoritmima i njihovom složenošću.
  • Sadrži teme kao što su: složenost algoritama, podatkovne strukture, vrste algoritama, algoritmi za sortiranje, drveća i grafovi, algoritmi za stabla i grafove.

Sadržaj

  • Složenost algoritama: analiza vremena izvršenja algoritama.
  • Podatkovne strukture: načini organizacije podataka za efikasno korišćenje.
  • Vrste algoritama: raznovrsni algoritmi prilagođeni različitim problemima.
  • Algoritmi za sortiranje: tehnike za sortiranje podataka (npr. brzo sortiranje, spajanje sortiranje).
  • Drveća i grafovi: strukture podataka za predstavljanje relacija između podataka.
  • Algoritmi za stabla i grafove: algoritmi za rad sa drvećima i grafovima (npr. pretraga grafom).

Ocjena

  • Laboratorijske vježbe: 20%
  • Domaći zadaci/projekti: 20%
  • Završni ispit: 60%
  • Aktivnost u nastavi: 10%

Literatura

  • The Algorithm Design Manual od Stevena S. Skiene (2008).
  • Introduction to Algorithms, 3rd Edition od Cormena, Leisersona, Rivest i Steina (2009).

Osnovni koncepti o algoritmima

  • Algoritmi: algoritam je korak-po-korak postupak za rješavanje problema.
  • Ulazni podaci: podaci koji se koriste kao ulaz u algoritam.
  • Izlazni podaci: rezultati dobijeni primjenom algoritma na ulazne podatke.
  • Složenost algoritama: mjera koliko je algoritam efikasan u vremenskom i prostorom pogledu.

Određivanje složenosti algoritama

  • Brojanje koraka: mjera složenosti algoritama se određuje brojanjem potrebnih operacija.
  • O(n): oznaka za opisivanje složenosti algoritama, gdje se uzima najveći stepen izraza.
  • Primjeri složenosti: O(1), O(log n), O(n), O(n log n), O(n²), O(n³).

Druge note

  • Postoje i druge metode mjerenja složenosti algoritama kao što su O-notacija, ω-notacija, Θ-notacija, itd.
  • Algoritmi mogu biti efikasni ili neefikasni
  • Efikasnost se mjeri vremenskom i prostornom složenošću.
  • Složenost algoritama se može opisati pomoću notacije O, Ω, Θ.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Algoritmi i kompleksnost PDF

Description

Ovaj kviz se fokusira na analizu algoritama i njihovih složenosti. Kroz razne teme kao što su podatkovne strukture, vrste algoritama, i algoritmi za sortiranje, testira se vaše znanje o efikasnom korišćenju podataka. Pripremite se za ispit i laboratorijske vježbe uz ovaj izazovan kviz.

More Like This

Sorting Algorithms Overview
12 questions

Sorting Algorithms Overview

SmoothestGrossular avatar
SmoothestGrossular
Data Structures and Algorithms Quiz
5 questions

Data Structures and Algorithms Quiz

PurposefulGothicArt avatar
PurposefulGothicArt
Algorithm Time Complexities Quiz
29 questions

Algorithm Time Complexities Quiz

CourteousSatire2150 avatar
CourteousSatire2150
Algorithm Time Complexities Quiz
53 questions

Algorithm Time Complexities Quiz

FormidableSage avatar
FormidableSage
Use Quizgecko on...
Browser
Open
Browser
Browser