Witam,
Mam do zrobienia zadania związane z asymptotyką w matematyce dyskretnej, jednakże nie do końca rozumiem co mam tu tak na prawdę zrobić. Jeżeli były ktoś tak miły wytłumaczyć prostymi słowami jak to zrobić (a najlepiej rozwiązał jakieś krok po kroku tak abym mógł przenalizować tok)
1. \(e^{\ln 855 + \ln(n!)} = Ω\left(592\ln\left(e^{473^n}\right)\right)\)
2. \(310n^{\frac{1}{731}} = O\left(7(n \ln n)\right)\)
3. \(e^{\ln 161 + \ln(n^{\ln n})} = \theta\left(\ln(\ln^{509} n)\right)\)
4. \(\ln(n^{745}) = o(884812^n)\)
Z góry dziękuję za pomoc
Asymptotyka zadania
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
janusz55
- Fachowiec
- Posty: 1561
- Rejestracja: 01 sty 2021, 09:38
- Podziękowania: 2 razy
- Otrzymane podziękowania: 412 razy
Re: Asymptotyka zadania
\( 1< log(n)< \sqrt{n}< n < n\cdot log(n)< n^2 < n^3< \ \ ... \ \ <2^{n}< 3^{n} < \ \ ... \ \ < n! < n^{n}.\)
1.
\( e^{\ln 855 + \ln(n!)} = \Omega\left(592\ln\left(e^{473^n}\right)\right)\)
\( f(n) = \Omega(g(n)) \Longleftrightarrow \exists (c, n_{0} = const) \forall (n \geq n_{0}) \ \ f(n) \geq c\cdot g(n).\)
\( f(n) = e^{\ln(855) + \ln(n!)} = 855\cdot n! \geq 592\cdot 473^{n} \cdot 1 = 592\cdot 473^{n} \cdot\ln(e) = 592 \cdot \ln\left(e^{473n}\right).\)
\( e^{\ln 855 + \ln(n!)} = \Omega\left(592\ln\left(e^{473^n}\right)\right), \ \ c = 592.\)
2.
\( 310n^{\frac{1}{731}} = O\left(7(n \ln n)\right)\)
\( f(n) = O(g(n)) \Longleftrightarrow \exists (c, n_{0} = const) \ \ \forall (n \geq n_{0}) \ \ f(n) \leq c\cdot g(n)\) (symbol Bachmanna-Landaua).
\( f(n) = 310n^{\frac{1}{731}} = 310\sqrt[731]{n} \leq 310\cdot n \leq 310 n\cdot \ln(n) \leq 420n\cdot \ln(n) = 60\cdot 7n\ln(n) = O(7n\ln(n)), \ \ c = 60.\)
3.
\( e^{\ln 161 + \ln(n^{\ln n})} = \theta\left(\ln(\ln^{509} n)\right)\)
\( f(n) = \theta(g(n)) \Longleftrightarrow \exists (c_{1}, c_{2}, n_{0} = const) \forall (n \geq n_{0}) \ \ c_{1}\cdot g(n)\leq f(n) \leq c_{2}\cdot g(n).\)
\( f(n) = e^{\ln 161 + \ln(n^{\ln n})} = 161\cdot n^{\ln(n)}.\)
\( 1\cdot n^{\ln(n)} \leq 161n^{\ln(n)} \leq 509\ln(\ln(n)) \leq 509\cdot \ln(n), \ \ c_{1} = 1, \ \ c_{2} = 509.\)
4.
\(\ln(n^{745}) = o(884812^n) \)
\( f(n) = o(g(n)) \Longleftrightarrow \forall ( c>0) \exists( n>0 ) \forall (n>n_{0} \ \ ( 0 \leq f(n) \leq c\cdot g(n)\) (symbol Bachmanna-Landaua).
lub
\( \Lim_{x\to x_{0}} \frac{f(x)}{g(x)} = 0 \)
\( f(n) = \ln(n^{745}) = 745\ln(n) \leq 745\cdot 884812^{n}, \ \ c = 745.\)
lub
\( \Lim_{n\to \infty} \frac{\ln \left(n^{745}\right)}{884812^{n}} = 0.\)
1.
\( e^{\ln 855 + \ln(n!)} = \Omega\left(592\ln\left(e^{473^n}\right)\right)\)
\( f(n) = \Omega(g(n)) \Longleftrightarrow \exists (c, n_{0} = const) \forall (n \geq n_{0}) \ \ f(n) \geq c\cdot g(n).\)
\( f(n) = e^{\ln(855) + \ln(n!)} = 855\cdot n! \geq 592\cdot 473^{n} \cdot 1 = 592\cdot 473^{n} \cdot\ln(e) = 592 \cdot \ln\left(e^{473n}\right).\)
\( e^{\ln 855 + \ln(n!)} = \Omega\left(592\ln\left(e^{473^n}\right)\right), \ \ c = 592.\)
2.
\( 310n^{\frac{1}{731}} = O\left(7(n \ln n)\right)\)
\( f(n) = O(g(n)) \Longleftrightarrow \exists (c, n_{0} = const) \ \ \forall (n \geq n_{0}) \ \ f(n) \leq c\cdot g(n)\) (symbol Bachmanna-Landaua).
\( f(n) = 310n^{\frac{1}{731}} = 310\sqrt[731]{n} \leq 310\cdot n \leq 310 n\cdot \ln(n) \leq 420n\cdot \ln(n) = 60\cdot 7n\ln(n) = O(7n\ln(n)), \ \ c = 60.\)
3.
\( e^{\ln 161 + \ln(n^{\ln n})} = \theta\left(\ln(\ln^{509} n)\right)\)
\( f(n) = \theta(g(n)) \Longleftrightarrow \exists (c_{1}, c_{2}, n_{0} = const) \forall (n \geq n_{0}) \ \ c_{1}\cdot g(n)\leq f(n) \leq c_{2}\cdot g(n).\)
\( f(n) = e^{\ln 161 + \ln(n^{\ln n})} = 161\cdot n^{\ln(n)}.\)
\( 1\cdot n^{\ln(n)} \leq 161n^{\ln(n)} \leq 509\ln(\ln(n)) \leq 509\cdot \ln(n), \ \ c_{1} = 1, \ \ c_{2} = 509.\)
4.
\(\ln(n^{745}) = o(884812^n) \)
\( f(n) = o(g(n)) \Longleftrightarrow \forall ( c>0) \exists( n>0 ) \forall (n>n_{0} \ \ ( 0 \leq f(n) \leq c\cdot g(n)\) (symbol Bachmanna-Landaua).
lub
\( \Lim_{x\to x_{0}} \frac{f(x)}{g(x)} = 0 \)
\( f(n) = \ln(n^{745}) = 745\ln(n) \leq 745\cdot 884812^{n}, \ \ c = 745.\)
lub
\( \Lim_{n\to \infty} \frac{\ln \left(n^{745}\right)}{884812^{n}} = 0.\)
Re: Asymptotyka zadania
Witam, dzięki za rozwiązanie, dużo mi pomogło, ale mam jedno pytanie dlaczego w przykładzie 3 linijka 4 mamy c1 × f(n) ⩽ f(n) ⩽ c2 × g(x). Skoro we wzorze jest inaczej. Nie rozumiem dlaczego tam na początku jest 1 × n^ln(n).
-
janusz55
- Fachowiec
- Posty: 1561
- Rejestracja: 01 sty 2021, 09:38
- Podziękowania: 2 razy
- Otrzymane podziękowania: 412 razy
Re: Asymptotyka zadania
Definicja symbolu \( "\theta" \) jest poprawna.
Dobieramy takie stałe \( c_{1}, c_{2} \) tak, aby zachodziła nierówność podwójna. Stałą \( c_{1} \) możemy wziąć na przykład:\( 2,10, 100,..., \ \ 508. \)
Proszę zauważyć, że wykorzystujemy nierówność \( \ln(\ln(n)) \leq \ln(n), \) dla \( n\in\nn_{+}.\)
Dobieramy takie stałe \( c_{1}, c_{2} \) tak, aby zachodziła nierówność podwójna. Stałą \( c_{1} \) możemy wziąć na przykład:\( 2,10, 100,..., \ \ 508. \)
Proszę zauważyć, że wykorzystujemy nierówność \( \ln(\ln(n)) \leq \ln(n), \) dla \( n\in\nn_{+}.\)