लॉग श्रृंखला के वर्ग के योग की गणना कैसे

Question

मैं एक एल्गोरिथ्म है, और मुझे पता लगा है कि अपनी चलाने के समय जटिलता निम्न सूत्र इस प्रकार है:

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 

लॉग के आधार 2.

है

मैं कैसे पता लगा सकता हूं कि Θ/और Omicron क्या है; एल्गोरिदमिक जटिलता इस सूत्र से है?

Answer 1

ऊपरी बाध्य आप similat लॉग इन करने के कारण कर सकते हैं (एन) = ओ (nlog (एन))

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 < [log(n)]^2 + ... + [log(n)]^2 
                  = n[log(n)]^2 

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 = O(n[log(n)]^2) 

लोअर बाउंड के लिए साबित करने के लिए, कि दिए गए योग दिखाने की जरूरत है> = लगातार कई के लिए

n [लॉग (एन)] का^2

राशि

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= [log(n/2)]^2 + [log(n/2 + 1)]^2 + [log(3)]^2 + ....... + [log(n)]^2 

से मामले की पहली छमाही हटाया जा रहा है लॉग (एन/2)^2

साथ प्रत्येक शब्द की जगह

[log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2 >= (n/2) * [log(n/2)]^2 

लोअर बाध्य = (n/2) * [log(n) - 1]^2

हम साबित कर सकते हैं कि log(n) - 1 >= (1/2) * log(n)

इसलिए कम (n/8) * [log(n)]^2 बाध्य = और ऊपरी बाध्य = n * [log(n)]^2

तो Θ([log(1)]^2 + [log(2)]^2 + [log(3)]^2 + ....... + [log(n)]^2) = n * [log(n)]^2