Là nhật ký (n!) = Θ (n · log (n))?

Question

tôi để chứng minh rằng log (n !) = Θ (n · log (n )).

Một gợi ý được đưa ra rằng tôi nên hiển thị trên ràng buộc với nⁿ và hiển thị các ràng buộc thấp với (n/2) ^(n/2) . Điều này dường như không trực quan với tôi. Tại sao điều đó lại xảy ra? Tôi chắc chắn có thể xem làm thế nào để chuyển đổi nⁿ để n · log (n ) (ví dụ: đăng nhập cả hai bên của một phương trình), nhưng đó là loại làm việc về phía sau.

Cách tiếp cận chính xác để giải quyết vấn đề này là gì? Tôi có nên vẽ cây đệ quy không? Không có gì đệ quy về việc này là, do đó không có vẻ như một cách tiếp cận có khả năng ..

Answer 1

Hãy nhớ rằng

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

Bạn có thể lấy trên ràng buộc bởi

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

Và bạn có thể nhận được giới hạn dưới bằng cách thực hiện một điều tương tự sau khi vứt bỏ nửa đầu của số tiền:

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) 

Answer 2

Th được có thể giúp:

 
eln(x) = x 

và

 
(lm)n = lm*n 

Answer 3

Xem Stirling's Approximation: (! n)

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

trong đó 2 cụm từ cuối cùng ít quan trọng hơn cụm từ đầu tiên.

Answer 4

Giúp bạn hơn nữa, nơi Mick Sharpe rời bạn:

Đó là deriveration là khá đơn giản: thấy http://en.wikipedia.org/wiki/Logarithm -> Nhóm Lý thuyết

log = log (n * (n (n!) 1) * (n-2) * ... * 2 * 1) = nhật ký (n) + nhật ký (n-1) + ... + nhật ký (2) + log (1)

Hãy suy nghĩ của n là cực lớn. Điều gì là vô hạn trừ một? hoặc trừ hai? v.v.

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

Và sau đó nghĩ về inf như n.

Answer 5

http://en.wikipedia.org/wiki/Stirling%27s_approximation So sánh xấp xỉ có thể giúp bạn. Nó thực sự hữu ích trong việc đối phó với các vấn đề về giai thừa liên quan đến số lượng lớn các đơn đặt hàng 10^10 trở lên.

Answer 6

Tôi nhận ra đây là một câu hỏi rất cũ với một câu trả lời được chấp nhận, nhưng không ai trong số những câu trả lời thực sự sử dụng phương pháp được đề xuất bởi các gợi ý.

Đó là một cuộc tranh luận khá đơn giản:

n! (= 1 * 2 * 3 * ... * n) là một sản phẩm của n số mỗi ít hơn hoặc bằng n. Do đó, nó nhỏ hơn sản phẩm của số n tất cả bằng n; tức là, n^n.

Một nửa số - nghĩa là n/2 trong số đó - trong sản phẩm n! lớn hơn hoặc bằng n/2. Do đó, sản phẩm của họ lớn hơn sản phẩm của n/2 tất cả các số bằng n/2; tức là (n/2)^(n/2).

Ghi nhật ký trong suốt để thiết lập kết quả.

Answer 7

Cảm ơn, tôi tìm thấy câu trả lời của bạn thuyết phục nhưng trong trường hợp của tôi, tôi phải sử dụng Θ tính:

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

để xác minh vấn đề tôi thấy web này, nơi bạn có tất cả các quá trình giải thích: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

Answer 8

Đối với ràng buộc thấp hơn,

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 n lg - 1)

Kết hợp cả hai giới hạn:

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

Bằng cách lựa chọn liên tục thấp hơn ràng buộc lớn hơn (1/2), chúng tôi (n!) có thể bù cho -1 bên trong khung.

Như vậy lg (n!) = Theta (n lg n)

Answer 9

Xin lỗi, tôi không biết làm thế nào để sử dụng cú pháp LaTeX trên stackoverflow ..