Naloge iz zahtevnosti algoritmov

Te naloge so namenjene dodatnemu utrjevanju snovi. Nalog ni potrebno oddati.

Naloga 1

Dopolni spodnjo tabelo in primerjaj med seboj naraščanje različnih funkcij.

\(n\) \(\log_2 n\) \(n\log_2 n\) \(n\) \(n^2\) \(n^3\) \(2^n\) \(n!\) \(n^n\)
\(1\) \(1\)
\(2\) \(2\)
\(3\) \(3\)
\(5\) \(5\)
\(10^1\) \(10^1\)
\(10^2\) \(10^2\)
\(10^3\) \(10^3\)
\(10^4\) \(10^4\)
\(10^5\) \(10^5\)
\(10^6\) \(10^6\)
\(10^9\) \(10^9\)

Naloga 2

Uredi podane funkcije po vrsti tako, da bo veljalo \(f_i=\Omega(f_{i+1})\):

a) Lažji del

\( 2^{2^n}, \ \ \ n^2, \ \ \ \lg n, \ \ \ (3/2)^n, \ \ \ \lg^2 n, \ \ \ n!, \ \ \ \lg \lg n, \ \ \ e^n, \ \ \ n \lg n, \)

\( n 2^n, \ \ \ n^3, \ \ \ 2^n, \ \ \ n, \ \ \ 1, \ \ \ (n+1)!, \ \ \ n \log n, \ \ \ 2^{2^{n+1}}, 42, \ \ \ n^n, \ \ \ \sqrt{n} \)

b) Težji del (dodaj v zgornji seznam)

\( 2^{\lg n}, \ \ \ (\lg n)!, \ \ \ (\sqrt{2})^{\lg n}, \ \ \ n^{1/\lg n}, \ \ \ \sqrt{\lg n}, \ \ \ 2^{\sqrt{\lg n}}, \ \ \ n^{\lg n}, \ \ \ \lg (n!), \ \ \ (\lg n)^{\lg n}, \ \ \ n^{1/n} \)

Naloga 3

Dan je algoritem, ki za nalogo velikosti \(n\) porabi \(f( n)\) mikrosekund, in naloga velikosti \(n=1000\). Koliko časa porabi algoritem za izračun rešitve?

\(f(n)\) \(\log n\) \(\sqrt{ n}\) \(n\) \(n \log n\) \(n^2\) \(n^3\) \(2^n\) \(n!\)
\(t\)

Naloga 4

Algoritem za izračun rešitve naloge velikosti \(n\) porabi \(f( n)\) mikrosekund. Kako velika je lahko naloga, da se algoritem konča v \(1\) sekundi?

\(f(n)\) \(\log n\) \(\sqrt{ n}\) \(n\) \(n \log n\) \(n^2\) \(n^3\) \(2^n\) \(n!\)
\(n\)

Naloga 5

  • Kakšna je časovna in prostorska zahtevnost algoritma iskanja največjega elementa v tabeli velikosti \(n\)?
  • Kolikšna je časovna zahtevnost dvojiškega iskanja v urejeni tabeli velikosti \(n\)?



Last modified: Monday, 26 February 2018, 8:56 AM