Jaka jest szybkość wzrostu funkcji:
a) t[n]=2*t[n/2] dla n>1 oraz t[1]=1
b) t[n]=t[n-1]+1/n dla n>1 oraz t[1]=1
??
IMO szybkosc wzrostu(zmiany) funkcji = pochodna...
johny_bravo napisał(a)
IMO szybkosc wzrostu(zmiany) funkcji = pochodna...
Dokładnie ale ponieważ funkcje, są w formie równania funkcyjnego więc pochodną też najłatwiej przedstawić w ten sposób:
a)t'[n]=t'[n/2]
b)t'[n]=t'[n-1]-1/n^2
:-)
Czyli jak to ? Jak mamy n/2 to będzie -n/4 ?
Jeśli oznaczyć by t'[n] = t[n+1] - t[n], to:
a)
przy n parzystych
t'[n] = t[n+1] - t[n] = 2*(t[(n+1)/2] - t[n/2]) = 2*(t[n/2] - t[n/2]) = 0
przy n nieparzystych troche gorzej, bo
t'[n] = t[n+1] - t[n] = 2*(t[(n+1)/2] - t[n/2]) = 2*(t[n/2 + 1] - t[n/2]) = 2 * t'[n/2]
Jeśli przyjrzeć by się wartościom:
n t[n] t'[n]
1 1 1
2 2 0
3 2 2
4 4 0
5 4 0
6 4 0
7 4 4
8 8 0
9 8 0
10 8 0
11 8 0
12 8 0
13 8 0
14 8 0
15 8 8
16 16 0
widać, że dla n = 2^m - 1 (gdzie m jest całowite) t'[n] = (n + 1) / 2
a dla pozostałych t'[n] = 0
b) t'[n] = t[n+1] - t[n] = t[n+1-1] + 1/(n+1) - t[n] = 1/(n+1)
ale to skomplikowane - nie rozumiem o co w tym chodzi, nie wiem po co ta pochodna :|
Przecież pochodna funkcji jednej zmiennej jest właśnie szybkością zmian danej funkcji.
Określ może do czego ci to jest potrzebne.
Takie zadanie po prostu mam - ale nie bardzo rozumiem - skoro rozwiązanie tego zadania to:
a)t'[n]=t'[n/2]
b)t'[n]=t'[n-1]-1/n^2
to w takim razie czym że jest to co wydaje mi się skomplikowane a co napisał adf88 ?
a)t'[n]=t'[n/2]
b)t'[n]=t'[n-1]-1/n^2
Ale to jest źle, to nie są "zwykłe" funkcje. Dziedziną są liczby naturalne. n/2 to nie jest zwykłe dzielenie tylko dzielenie bez reszty (zróżniczkuj sobie takie dzielenie ;) ). Poza tym (t[n-1])' to nie t'[n-1]
Rozwiązanie tp:
a)
t'[n] = (n + 1) / 2, dla n = 1, 3, 7, 15, 31 ...
t'[n] = 0, dla n <> 1, 3, 7, 15, 31 ...
b)
t'[n] = 1/(n+1)
adf88 a nie ma jakiegoś prostszego sposobu oszacowania szybkości wzrostu funkcji ?
Hę ? przecież ten sposób jest najprostszy z możliwych. O ile w a) jest to zbadane empirycznie, to w b jest to tylko 1 linijka dowodu:
t'[n] = t[n+1] - t[n] = t[n+1-1] + 1/(n+1) - t[n] = 1/(n+1)
I nie jest to oszacowanie a dokładny wynik.
Zadanie na poziomie gimnazjum, gdzie tu coś skomplikowanego ????
No dziękuję adf88 - ten podpunkt A wydaje się trudny.
Np. tam jak jest dla "n" nieparzystych t[(n+1)/2] to potem przechodzi w t[n/2+1], ale dla np. "5": 5/2+1 to wyjdzie 3.5.
5/2+1 = 2+1 = 3 = (5+1)/2 jeśli mowa o całkowitych. A nie ? No bo jeśli n ma być rzeczywiste, to wszystko co napisałem do kosza się nadaje. Zapis sugeruje, że n ma być całkowite (nawiasy kwadratowe, literka n). Więc jakie to n jest ?
tak "n" jest całkowite - wielkie dzięki za wszystkie wyjaśnienia - teraz rozumiem :) Dzięki adf88 :D