Naloge iz zahtevnosti algoritmov

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

Naloga 1

Dopolnite spodnjo tabelo in primerjajte 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

Uredite 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 (dodajte 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\)?

Zadnja sprememba: petek, 28. februar 2025, 11.06