Ar log (n!) = Θ (n · log (n))?

Turiu parodyti, kad log (n!) = Θ (n · log (n)) .

Pateikta nuoroda, kad turėčiau parodyti viršutinę ribą n n ir parodyti apatinę ribą (n / 2) (n / 2) . Man atrodo neįdomu. Kodėl taip yra? Aš tikrai galiu pamatyti, kaip konvertuoti n n į n · log (n) (t.y. įrašyti abi lygtis), tačiau šis darbas yra atvirkščiai.

Koks bus teisingas požiūris į šią problemą? Ar turėčiau piešti rekursijos medį? Nėra nieko apie rekursiją, taigi jis neatrodo patikimas.

181
19 янв. Mark 19 Jan. 2010-01-19 20:15 '10, 20:15, 2010-01-19 20:15
@ 10 atsakymų

Atminkite, kad

 log(n!) = log(1) + log(2) + ... + log(n-1) + log(n) 

Galite gauti viršutinę ribą.

 log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n) = n*log(n) 

Ir jūs galite gauti apatinę ribą, atlikdami tą patį dalyką, išmesti pirmąją sumos pusę:

 log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n) >= log(n/2) + ... + log(n/2) = n/2 * log(n/2) 
249
19 янв. Atsakymą Mick pateikė sausio 19 d. 2010-01-19 20:23 '10, 20:23, 2010-01-19 20:23

Suprantu, kad tai yra labai senas klausimas su priimtinu atsakymu, tačiau nė vienas iš šių atsakymų nenaudoja patarimo, kurį pasiūlė patarimas.

Tai gana paprastas argumentas:

n! (= 1 * 2 * 3 * ... * n) yra skaičius n , kurio kiekvienas yra mažesnis arba lygus n . Todėl jis yra mažesnis už produktą, kurio skaičius n lygus n ; t.y. n^n .

Pusė jų - t.y. n/2 iš jų - gaminyje n! didesnė arba lygi n/2 . Todėl jų produktas yra didesnis nei skaičius n/2 , visi yra lygūs n/2 ; t.y. (n/2)^(n/2) .

Norėdami nustatyti rezultatą, paimkite žurnalus.

35
03 нояб. atsakymas duotas Nemo 03 lapkričio. 2011-11-03 07:01 '11 at 7:01 am 2011-11-03 07:01

Žr. „ Stirling Approximation“ :

ln (n!) = n * ln (n) - n + O (ln (n))

paskutiniai 2 nariai yra mažiau reikšmingi nei pirmieji.

11
19 янв. atsakymas yra dsimcha 19 jan. 2010-01-19 20:51 '10, 20:51, 2010-01-19 20:51
09 янв. atsakymą pateikė Samuel 09 Jan 2017-01-09 21:25 '17 - 21:25 2017-01-09 21:25

Apatinė riba

 lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1 >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later) = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2 = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2 = n/2 lg n - 1/2 

lg (n!)> = (1/2) (n lg n - 1)

Derinant abi ribas:

1/2 (n lg n - 1) <= lg (n!) <= Ngg

Pasirenkant apatinę ribinę konstantą, didelę (1/2), galime kompensuoti -1 skliausteliuose.

Taigi, lg (n!) = Theta (n lg n)

5
21 февр. atsakymą pateikė Vivek Anand Sampath 21 vasaris. 2015-02-21 04:56 '15 at 4:56 2015-02-21 04:56

Padėti jums toliau, kai Mickas Sharpas paliko jus:

Šis išvestis yra gana paprasta: žr. Http://en.wikipedia.org/wiki/Logarithm → Grupės teorija

log (n!) = žurnalas (n * (n-1) * (n-2) * ... * 2 * 1) = log (n) + log (n-1) + ... + žurnalas (2 ) + žurnalas (1)

Pagalvokite apie n kaip be galo didelį. Kas yra begalinis minusas? arba minus du? ir kiti

žurnalas (inf) + žurnalas (inf) + žurnalas (inf) + ... = inf * log (inf)

Ir tada pagalvokite apie inf kaip n.

3
19 янв. Atsakymas duotas Pindatjuh 19 sausio. 2010-01-19 21:25 '10, 21:25, 2010-01-19 21:25

Ačiū, suradau jūsų atsakymus įtikinamais, bet mano atveju turėčiau naudoti šias savybes:

 log(n!) = Θ(n·log n) => log(n!) = O(n log n) and log(n!) = Ω(n log n) 

patikrinti problemą, kurią rado šiame tinkle, kuriame paaiškinote visą procesą: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

2
21 марта '14 в 12:12 2014-03-21 12:12 atsakymą pateikė WyrmxD kovo 21 d., 14 val. 12:12 2014-03-21 12:12

Tai gali padėti:

 e ln (x) = x

ir

 (l m ) n = l m * n 
1
19 янв. atsakymas pateikiamas Anycorn Jan 19 2010-01-19 20:33 '10, 20:33, 2010-01-19 20:33

Aš supainioti su pirmuoju atsakymu: kaip ir kodėl mes galime išmesti pirmąją pusę sumos?

0
03 февр. Atsakymas pateikiamas kscs 03 vasario mėn. 2019-02-03 21:16 '19, 21:16 pm 2019-02-03 21:16

http://en.wikipedia.org/wiki/Stirling%27s_approximation „ Stirling“ perėjimas gali jums padėti. Tai tikrai naudinga sprendžiant su faktais susijusių problemų, susijusių su dideliu skaičiumi nuo 10 ^ 10 ir didesnių, problemomis.

2019

0
03 нояб. Atsakymą pateikė user302520 03 Nov. 2011-11-03 06:53 '11 at 6:53 2011-11-03 06:53