z
Kamil: udowodnij że:
log(n!)=O(nlogn)
log(1*2*3*...*n)= log1+log2+...+logn (1)
z tw o 3 ciągach umiem ograniczyć z góry, ale nie wiem jak z dołu
(1)<logn+logn+...=nlogn
30 lis 21:08
30 lis 21:13
Mariusz:
Kamil analiza algorytmów ?
Przykładowo sortowania mają złożoność log(n!)
a zapisywane jest to jako O(nlogn)
1 gru 01:31
iteRacj@:
log(n!)=log(1*2*3*...*n)= log 1+log 2+...+log(n)
n*log(n)=log (n
n)=log(n)+log(n)+...+log(n)
| | log(n!) | | log 1+log 2+...+log(n) | |
limn→∞= |
| = |
| |
| | n*log(n) | | n*log(n) | |
| | log 1 | | log 2 | | log(n) | |
= |
| + |
| +...+ |
| =0 |
| | n*log(n) | | n*log(n) | | n*log(n) | |
log(n!)=O(nlog(n))
1 gru 08:58
jc: Połowa czynników w n! jest większa od n/2.
Dlatego n! ≥ (n/2)n i ln n! ≥ n ln n − n ln 2.
To powinno wystarczyć.
1 gru 09:14
Kamil: Mariusz − tak, to analiza złożoności algorytmu.
Dzięki wszystkim za pomoc
1 gru 09:41
Adamm:
@iteRacja
Czym uzasadniona jest ostatnia równość?
Zgaduję że "suma składników dążących do 0 dąży do 0", co nie jest prawdą
gdy ta suma rośnie
1 gru 13:16
Adamm:
| | log1+...+logn | | log(n+1) | |
lim |
| = lim |
| = |
| | nlogn | | (n+1)log(n+1)−nlogn | |
1 gru 13:19
iteRacj@:
dobrze zgadłeś, dziękuję za poprawienie błędu!
1 gru 13:25