Algoritmuselmélet - PPZH, 2013.05.23.

← Vissza az előző oldalra – Algoritmuselmélet

2013.05.23 - PPZH megoldásai

1. Feladat (Van megoldás)

Tudjuk, hogy az [math] f(n), g(n) : \textsc{N} \rightarrow \textsc{N} [/math] függvényekre igaz, hogy [math] f(n)= \Omega (logn) [/math] és [math] g(n) = \Theta (n^4) .[/math] Lehetséges-e, hogy:

(a) [math] f(n) = \Theta (g(n)) ?[/math]

(b) [math] g(n) = O(f(n)) ?[/math]

(Ez két, egymástól függetlenül megválaszolandó kérdés.)

Megoldás

a)

• Ha [math] f(n) = n^4 , g(n) = n^4 [/math]
• Akkor igaz az, hogy:
  • [math] f(n)= \Omega (logn) \Rightarrow n^4 = \Omega (logn)[/math]
  • És az is, hogy [math] f(n) = \Theta (g(n)) \Rightarrow n^4 = \Theta (n^4)[/math]
• Tehát lehetséges.

b)

• Ha [math] g(n) = n^4 , f(n) = n^4 [/math]
• Akkor igaz az, hogy:
  • [math] g(n)= \Theta (n^4) \Rightarrow n^4 = \Theta (n^4)[/math]
  • És az is, hogy [math] g(n) = O(f(n)) \Rightarrow n^4 = O(n^4)[/math]
• Tehát lehetséges.

2. Feladat

TODO

Megoldás

TODO

3. Feladat

TODO

Megoldás

TODO

4. Feladat

TODO

Megoldás

TODO

5. Feladat

TODO

Megoldás

TODO

6. Feladat

TODO

Megoldás

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO