Witam,
mam problem z tymi przykładami:
Jaką ma notację \(\displaystyle{ \theta}\)?
a)\(\displaystyle{ (6n+4)(1+\log n)}\)
b) \(\displaystyle{ 25\log (2n+10)}\)
Oczywiście, że znam definicję:
\(\displaystyle{ c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)}\)
Co do a) to:
\(\displaystyle{ (6n+4)(1+\log n)=6n+6n \log n+4+4 \log n}\) Nie wiem, jak to wyznaczyć, jest logarytm.
Nie prosiłabym o pomoc, gdyby były w internecie sporo przykładów, to bym poradziła. A to tak, jest niewiele.
Byłabym wdzięczna, żebyś ktoś ładnie to wytłumaczył. Bardzo mi zależy na zrozumieniu tych przykładów.
[Teoria złożoności] Notacja - przykłady
-
nowik1991
- Użytkownik
- Posty: 268
- Rejestracja: 12 lis 2011, o 23:19
- Płeć: Mężczyzna
- Lokalizacja: o-o
- Podziękował: 23 razy
[Teoria złożoności] Notacja - przykłady
Nie dam sobie głowy uciąć ale...
\(\displaystyle{ (6n+4)(1+\log n)=\Theta(logn)}\)
Ale nie jestem pewien na 100%...drugi przykład rozpisałaś? Twój wzór na notację jest oczywiście okej ale zobacz, że on mówi nam po prostu tyle:
\(\displaystyle{ \Theta (g(n)) = O (g(n)) \cap \Omega (g(n))}\)
Z twoich wymnożeń wyszło, że wspólnym takim czynnikiem byłoby \(\displaystyle{ (logn+1)}\) dlatego wnioskuję,że jest to złożoność \(\displaystyle{ \Theta(logn)}\).
\(\displaystyle{ (6n+4)(1+\log n)=\Theta(logn)}\)
Ale nie jestem pewien na 100%...drugi przykład rozpisałaś? Twój wzór na notację jest oczywiście okej ale zobacz, że on mówi nam po prostu tyle:
\(\displaystyle{ \Theta (g(n)) = O (g(n)) \cap \Omega (g(n))}\)
Z twoich wymnożeń wyszło, że wspólnym takim czynnikiem byłoby \(\displaystyle{ (logn+1)}\) dlatego wnioskuję,że jest to złożoność \(\displaystyle{ \Theta(logn)}\).