Časovna Zahtevnost

Kakšna je časovna zahtevnost vstavljanja elementa (`.insert`) v tabelo dolžine n?

• $O\left(1\right)$

• $O\left(n\right)$
  

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

• Odvisno od indeksa vstavljanja.

Kaj je prednost dvojno povezanega verižnega seznama v primerjavi z enostavnim verižnim seznamom.

• Hitrejše vstavljanje.

• Brisanje zadnjega elementa je $O\left(1\right)$

• Dostop do zadnjega elementa je $O\left(\log\ n\right)$

• Boljša prostorska učinkovitost.

Obkljukajte operacije, ki so linearne glede na dolžino verižnega seznama.

• Minimum

• Brisanje prvega elementa

• Urejanje

• Število pojavitev elementa

Kakšna sta časovna in prostorska zahtevnost zgornje funkcije za vsoto elementov seznama?

• Časovno $O\left(n\right)$ in prostorsko $O\left(1\right)$

• Časovno $O\left(n\ \cdot\log\ n\right)$ in prostorsko $O\left(1\right)$

• Časovno $O\left(n\right)$ in prostorsko $O\left(n\right)$

• Časovno $O\left(n^2\right)$ in prostorsko $O\left(n^2\right)$

Za iskanje največjega elementa v skladu (kjer na koncu sklad ne spremeni oblike) potrebujemo

• $O\left(n\right)$ časa

• $O\left(\log\ n\right)$ časa

• $O\left(1\right)$ prostora

• $O\left(n\right)$ prostora

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

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

• $O\left(n\right)$

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

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

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

Kako poenostavimo časovno zahtevnost

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

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

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

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

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

Opišite zahtevnost zgornjega programa če je seznam dolžine n.

• Časovno $O\left(n\right)$

• Časovno $O\left(n^2\right)$

• Prostorsko $O\left(1\right)$

• Prostorsko $O\left(n\right)$

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

Kako hitro lahko uredimo seznam števil od 1 do n?

• $O\left(1\right)$

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

• $O\left(n\right)$

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

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

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

• $O\left(k\right)$

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

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