यह सीएलआरएस पुस्तक से एक समस्या है। एल्गोरिदम अध्ययन समूह वेबसाइट के परिचय ने इसका उत्तर दिया:
(http://clrs.skanev.com/04/problems/03.html)
क्या यह जवाब सही है? मैं पिछले दो लाइनों को समझ नहीं पा रहा हूं।
उत्तर:
जवाब के लिए 2 № 1नहीं यह नहीं। इसके अलावा वहां एक टाइपो है, अनंतता के बजाय एन होना चाहिए। सख्त गणितीय प्रमाण के लिए आपको किसी अन्य स्टैक एक्सचेंज साइट (गणितीय एक) पर पूछना चाहिए। लेकिन आपके अंतर्ज्ञान के लिए मैं निम्नलिखित दिखा सकता हूं।
चलो कल्पना करो कि n = 2^2^k फिर sum of 1/lg(i) के बराबर होती है
1/lg2 + 1/lg3 + 1/lg4 + 1/lg5 + 1/lg6 + 1/lg7 + 1/lg8 + 1/lg9 +
1/lg10 + 1/lg11 + 1/lg12 + 1/lg13 + 1/lg14 + 1/lg15 + ... + 1/lg n-1
और यह लगभग है
1/lg2 + 1/lg2 + 1/lg4 + 1/lg4 + 1/lg4 + 1/lg4 + 1/lg8 + 1/lg8 +
1/lg8 + 1/lg8 + 1/lg8 + 1/lg8 + 1/lg8 + 1/lg8 + ... + 1/lg n-1
के बराबर होती है
1/1 + 1/1 + 1/2 + 1/2 + 1/2 + 1/2 + 1/3 + 1/3 +
1/3 + 1/3 + 1/3 + 1/3 + 1/3 + 1/3 + ... + 1/ (2^k - 1) (as lg n = 2^k)
हमारे संयोजन के बाद
sum(1/i * 2^i) from 1 to 2^k-1
जहां अंतिम सदस्य है n/2 / 2^k-1 जो कुछ के बारे में है 2^(2^k-k-1) और यह बहुत दूर नहीं है lg lg n = k। और निश्चित रूप से पूरा योग भी बड़ा है।