Free Printable Rac 1 vaje 6

1.

Če ima nek algoritem časovno zahtevnost O(1), to pomeni:

a)

Da pri izvajanju algoritma opravimo eno operacijo.

b)

Da pri izvajanju algoritma uporabimo konstantno mnogo operacij.

c)

Da pri izvajanju algoritma uporabimo linearno mnogo operacij.

d)

Da pri izvajanju algoritma uporabimo eksponentno mnogo operacij.

2.

Ali dva različna algoritma s časovno zahtevnostjo $O\left(2\times n\right)$ in $O(100\times n)$ spadata v isto družino?

a)

Da

b)

Ne

3.

Kakšno pričakovano časovno zahtevnost ima algoritem na sliki (randint(sp,zm) ima ČZ O(1)):

a)

O(M)

b)

O(n)

c)

O(N+M)

d)

O(M*N)

4.

Časovna zahtevnost iskanja elementa v urejeni tabeli velikosti n z bisekcijo je?

a)

O(log n)

b)

O(n²)

c)

O(n)

d)

Nič od naštetega

5.

Označi stavke, ki vsaj približno opisujejo dogajanje v algoritmu, katerega pričakovana časovna zahtevnost je O(n²).

a)

Zanka v zanki.

b)

Pogojni stavek, kjer se v obeh vejah izvede zanka z n ponovitvami.

c)

Na seznamu n elementov za vsak element opravimo n primerjav.

6.

Najslabši primer pri linearnem iskanju nastopi ko:

a)

Je iskani element nekje na sredi seznama.

b)

Iskanega elementa ni v seznamu.

c)

Iskani element je prvi v seznamu.

d)

Iskanega elementa ni v seznamu ALI ko je iskani element zadnji v seznamu.

7.

Katera od naslednjih časovnih zahtevnosti ima najvišjo rast:

a)

O(n^1/2)

b)

O(n¹⁰⁰)

c)

O(2^n/2)

d)

O(2^n!)

8.

Kakšno pričakovano časovno zahtevnost ima naslednja koda?

a)

O(n³)

b)

O(n)

c)

O(n²)

d)

O(2ⁿ)

9.

Kakšno pričakovano zahtevnost ima naslednja koda:

a)

O(n²)

b)

O(2*n)

c)

O(n³)

d)

O(2ⁿ)

10.

Kakšna je časovna zahtevnost zgornje funkcije glede na število n?

a)

$O\left(n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(\log\ n\right)$

d)

$O\left(2^n\right)$

11.

Kako poenostavimo časovno zahtevnost

O\left(14\ n^2\ +\ 200n\ \cdot\log_{ }n\ +\ 2^n\right)

a)

$O\left(n\cdot\log\ n\right)$

b)

$O\left(n^2\right)$

c)

$O\left(n^2\ +\ 2^n\right)$

d)

$O\left(2^n\right)$

12.

Kakšna je časovna zahtevnost zgornjega programa, če je seznam dolžine n in je njegov največji element k.

a)

$O\left(n\ \cdot\ k\right)$

b)

$O\left(k\right)$

c)

$O\left(n\cdot\sqrt{k}\right)$

d)

$O\left(n^2\ \log k\right)$

Rac 1 vaje 6

Total questions: 12

Worksheet time: 9mins

Similar Resources on Wayground