rownanie rekurencyjne

pytanie zadane 15 grudnia 2020 w Rozwój zawodowy, nauka, praca przez dellek1 Nowicjusz (120 p.)

Prosze o wytłumaczenie rozwiązania tej rekurencji

Postać rekurencji: T(n) = 2T(n/2) + n

Zgadnięte rozwiązanie: T(n) = Θ(n log n)‏

Podstawa: n=2; T(1)=1; T(2)=4;

Indukcja: T(n) ≤ 2 (c(n/2)log(n/2)) + n ≤ c n log(n/2) + n T(n) ≤ c n log(n/2) + n = cn log(n) – cn log(2) + n T(n) ≤ cn log(n) – cn log(2) + n = cn log (n) – cn + n T(n) ≤ cn log (n) – cn + n ≤ cn log(n) spełnione dla c>=1;

komentarz 15 grudnia 2020 przez tkz Nałogowiec (42,040 p.)

https://www.youtube.com/watch?v=1K9ebQJosvo

komentarz 15 grudnia 2020 przez dellek1 Nowicjusz (120 p.)

zależy mi na wytłumaczeniu metody podstawiania zawartej w pytaniu

komentarz 15 grudnia 2020 przez tkz Nałogowiec (42,040 p.)

http://zsi.tech.us.edu.pl/~ppaszek/PLIKI/WSFIP/MD/st_MD-05_rekurencja.pdf slajd 8.. Właściwie filmik również o tym mówi.

komentarz 15 grudnia 2020 przez Wiciorny Ekspert (283,300 p.)

@dellek1, brakuje jeszcze Ci żebyś wiedział jak się "tworzy dowód przez indukcje" wtedy będziesz wiedział, metoda Lewej i prawej indukcji się przyda bo jest najprostsza dla np. n. n+1 czy n=k elementów

komentarz 16 grudnia 2020 przez dellek1 Nowicjusz (120 p.)

mógłbyś jakoś w skrócie opisać?

komentarz 16 grudnia 2020 przez dellek1 Nowicjusz (120 p.)

na przykładzie tej rekurencji

komentarz 16 grudnia 2020 przez Wiciorny Ekspert (283,300 p.)

https://pl.wikipedia.org/wiki/Indukcja_matematyczna
Na przykładzie który jest podobny :) a Ty masz zrozumieć, na przykładzie twojej rekurencji byłoby to rozwiązaniem zadania dla Ciebie co jest trywialne