समय जटिलता

Question

हाल ही में, मैं एक कोड का टुकड़ा भर में आया था:

int i = 1; 
while (N > 1) 
{ 
     N = N/i; 
     i = i + 1; 
} 

अवलोकन करने पर यह स्पष्ट है कि i बढ़ जाती है रैखिक, और i पाश के हर क्रम में N बांटता था, इसलिए हम कर सकते थे कहें कि Nफ़ैक्टोरियल के व्यस्त कार्य के फ़ंक्शन के रूप में कम हो जाता है।

हम इस थीटा अंकन में प्रतिनिधित्व करते हैं, के रूप में होगा उलटा भाज्य हर प्राकृतिक संख्या N के लिए निर्धारित नहीं है? क्या हमें इस समारोह के अनुमानित ऊपरी और निचले सीमाओं का उपयोग करके पर्याप्त होना होगा?

Answer 1

अच्छा, मुझे यकीन नहीं है, लेकिन मैं इसे एक शॉट दूंगा। फैक्टोरियल, संक्षेप में, gamma function है। और गामा फ़ंक्शन न केवल प्राकृतिक संख्याओं के लिए परिभाषित किया जाता है, बल्कि वास्तविक संख्याओं के लिए भी परिभाषित किया जाता है। इसलिए, सिद्धांत रूप में, एक व्यस्त गामा फ़ंक्शन है, जिसे मामलों के लिए परिभाषित किया गया है, जहां फैक्टोरियल अनिर्धारित है (उदाहरण के लिए, हम 5 के व्यस्त फ़ैक्टोरियल को नहीं जानते हैं, लेकिन हम जानते हैं कि 5 का व्यस्त गामा फ़ंक्शन होगा दो बिंदु-कुछ के आसपास कुछ हो)। MathOverflow के अनुसार, व्यस्त गामा फ़ंक्शन के लिए कोई सटीक सूत्र नहीं है, लेकिन अनुमानित समाधान हैं।

चलो बस मान लें कि व्यस्त गामा फ़ंक्शन मौजूद है, और इसे InvGamma(N) के रूप में लिखें। यह एक वास्तविक संख्या है (आर + हो सकता है, लेकिन मुझे यकीन नहीं है, अब यह महत्वपूर्ण नहीं है, क्योंकि एन एन == 0 मामले के अलावा, हमारे एन हमेशा सकारात्मक है, जिसे मैं अभी अनदेखा कर दूंगा)।

फिर हम इसका उपयोग उसी तरह कर सकते हैं जैसे हम वास्तविक संख्या को वापस करने वाले अन्य कार्यों का उपयोग करते हैं, जब हम जटिलता से निपटते हैं: हम floor इसे (इसे नीचे कर सकते हैं) कर सकते हैं। जैसे हम log जटिलता के साथ करते हैं। मैं स्क्वायर ब्रैकेट्स का उपयोग लिखता था (यानी log(15) = 1.18, [log(15)] = 1)।

तब आपके स्निपेट की जटिलता O([InvGamma(N)]) होनी चाहिए, मुझे विश्वास है।

अद्यतन: (@ 6502 के जवाब से प्रेरित): ध्यान दें कि यदि N एक पूर्णांक (यह कोड स्निपेट में उल्लेख नहीं किया गया है) है, तो हर कदम है, जो एक जटिल तरीके से जटिलता को बदल देता है पर एक गोलाई हो जाएगा । उपरोक्त समाधान वास्तविक N एस के लिए काम करता है।

Answer 2

नकारात्मक पूर्णांक को छोड़कर सभी जटिल विमानों के लिए फैक्टोरियल का "प्राकृतिक" विस्तार "gamma function" और सभी गैर-ऋणात्मक पूर्णांक gamma(n) = (n-1)! पर रखा जाता है।

इसलिए जरूरत पुनरावृत्तियों की अनुमानित संख्या की गणना करने के गामा के एक हिस्से को उलटने सकता है, लेकिन मुझे यकीन है कि यह एक सटीक पुनरावृत्तियों की संख्या की गणना करने के लिए नेतृत्व करेंगे नहीं कर रहा हूँ कि कोड में के रूप में वहाँ पर एक पूर्णांकन ऑपरेशन है हर कदम।