WorksheetsKviz o časovni zahtevnosti /Računalništvo 1/
Total questions: 15
Worksheet time: 11mins
Kakšna je pričakovana časovna zahtevnost naslednje kode?
O(N)
O(√N)
O(log(N))
O(N/2)
Kakšna je pričakovana časovna zahtevnost kode na sliki?
O(N*N)
O(N + M)
O(N*M)
O( max(N,M))
Imamo enostaven, enojno povezan verižni seznam z n elementi. Poznamo kazalec na m-ti element, ki bi ga radi izbrisali (element, ne kazalca). Kakšna bo časovna zahtevnost tega algoritma?
O(n)
O(m)
O(1)
O(log(n))
Funkcija, ki sprejme tabelo velikosti M in neko vrednost, ter vrne kolikokrat se v tabeli pojavi element z to vrednostjo, ima kakšno najmanjšo časovno zahtevnost?
O(M)
O(1)
O(M*log(M))
O(√M)
Pri katerih vhodnih podatkih bo algoritem na sliki deloval najhitreje?
tab = [1, 2, ... , n-1, n] , vrednost = n
tab = [2, 4, ... , 2*n -2, 2*n], vrednost = n
tab = [n, n-1, ..., 2, 1], vrednost = n
tab = [n, n-1, ..., 2, 1], vrednost = 1
Časovna zahtevnost urejanja z mehurčki je v najslabšem primeru:
O(n)
O(n2)
O(n*log(n))
O(2n)
O(n3)
Algoritem A je asimptotično bolj učinkovit kot B. Kaj to pomeni?
A bo vedno boljši pri majhnem številu vhodnih podatkov
A bo vedno boljši pri velikem številu vhodnih podatkov
B bo vedno boljši pri malem številu vhodnih podatkov
A bo vedno boljši ne glede na število vhodnih podatkov
Ali so naslednje časovne zahtevnosti pravilno razporejene po rasti?
O(log(n)), O(√n), O(n * log(n)), O(n!), O(2n)
Da
Ne
T1, T2,T3, T4 in T5 predstavljajo število karakterističnih operacij petih algoritmov. Kateri izmed njih bo imel najslabšo časovno zahtevnost? Možnih je več pravilnih odgovorov.
T1(n) = 10*n2 + n + 5
T2(n) = 99999*n2 + 6
T3(n) = n * log(n) * √n + n
T4(n) = n* √n + 40
T5(n) = log(n2)
Kateri izmed naslednjih primerov časovne zahtevnosti spadajo v isto družino (možnih je več odgovorov):
T1(n) =(3n2 + 14n -3)
T2(n) = (5432n - 5432)
T3(n) = (13 + 3n2 - 2n)
T4(n) = (2n3 +4n2)
T5(n) = (3n -999*2n)
T6(n) = (n2 + 12)
T7(n) = (225n*log(n))
T8(n) = (15n)
T1, T3 in T6
T7 in T8
T4, T6, T7 in T8
T1 in T5
T2 in T8
Kakšna je časovna programa, ki na že urejenem seznamu dolžine n požene algoritem mergesort (urejanje z zlivanjem).
O(1)
O(n)
O(n*log(n))
nič od zgoraj naštetega.
Časovna zahtevnost tega, da na 2. mesto tabele dolžine n vrinemo element (z metodo tabela.insert(1, element)) je:
O(1)
O(n)
O(n2)
O(log(n))
Časovna zahtevnost tega, da na 2. mesto verižnega seznama dolžine n vrinemo element je:
O(1)
O(log(n))
O(n)
O(n2)
Kakšna je časovna zahtevnost kode na sliki?
O(n)
O(n*log(n))
O(n2)
O(log(n)*n2)
kakšno je največja časovna zahtevnost iskanja elementa v levo poravnanem iskalnem dvojiškem drevesu z n elementi?
O(1)
O(log(n))
O(n)
O(n*log(n))
