Rozwiąż złożoność rekurencyjną

sebointruz · Post autor: **sebointruz** » 29 sty 2011, o 12:02

T(n) = T(n-1)+lgn

sonicwork · Post autor: **sonicwork** » 29 sty 2011, o 13:29

w jakim języku ? mógłbyś też napisać o co dokładnie chodzi... czy masz napisać program który liczy taką funkcje po podaniu n ?

abc666 · Post autor: **abc666** » 29 sty 2011, o 13:40

sebointruz, po rozpisaniu

\(\displaystyle{ T(n)=T(0)+ \sum_{i=1}^{n}\lg i=T(0)+\lg n!}\)

No i teraz ze wzory Stirlinga

\(\displaystyle{ \lg n! \approx n\lg n - n\lg e + \frac{1}{2} \lg (2\pi n)}\)

sebointruz · Post autor: **sebointruz** » 29 sty 2011, o 14:19

dzięki abc666,
dlaczego
\(\displaystyle{ \sum_{i=1}^{n}=lg n!}\) ??
Czy nie powinno być:
\(\displaystyle{ \sum_{i=1}^{n}=\frac{lg + lgn}{2}n}\)

abc666 · Post autor: **abc666** » 29 sty 2011, o 16:11

\(\displaystyle{ \lg a+\lg b=\lg (a\cdot b)}\)
podstawowa własność logarytmu

sebointruz · Post autor: **sebointruz** » 29 sty 2011, o 17:48

własność algorytmu masz dobrą ale złe zastosowanie bo:
nie prawdą jest że:

\(\displaystyle{ \sum_{i=0}^{n}lgn=lg(n!)}\)
uważam że
\(\displaystyle{ \sum_{i=0}^{n}lgn=nlgn}\)

abc666 · Post autor: **abc666** » 29 sty 2011, o 19:41

Oj no tam w argumencie \(\displaystyle{ i}\) miało być, tak bym tej sumy nie pisał.