Teorija 3: povzetek prosojnic
Naloga 1
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\) |
Čas po potrebi pretvori v človeku predstavljivo enoto.
Naloga 2
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 3
Z uporabo definicije pokaži, da je ali ni \( f(x) = O(g(x)) \), če je\( f(x) = 3 x^2 + 7 x -1 \) in \(g(x)\) enako:
- \( g(x) = x^3 \)
- \( g(x) = x^2 \)
- \( g(x) = x \)
Naloga 4
Z uporabo definicije pokaži, da je ali ni \( f(x) =\Omega(g(x)) \), če je\( f(x) = 3 x^2 + 7 x -1 \) in \( g(x) \) enako:
- \( g(x) = x \)
- \( g(x) = x^2 \)
- \( g(x) = x^3 \)
Naloga 5
Z uporabo limit pokaži v kakšnem odnosu je \( f(x) = 3 x^2 + 7 x - 1 \) , če je \( g(x) \) enako:
- \( g(x) = x \)
- \( g(x) = x^2 \)
- \( g(x) = x^3 \)
- \( g(x) = lg x \)
- \( g(x) =2^x \)
Naloga 6
Z uporabo limit pokaži, da so:
- potence logaritma počasnejše od polinomov
- polinomi počasnejši od eksponentnih funkcij
Naloga 7
Uredi po vrsti tako, da bo veljalo \(f_i=\Omega(f_{i+1})\):
\( 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} \)