हास्केल

Question

में पूर्णकालिक जटिलता पिछले सप्ताह स्कूल में एक असाइनमेंट था ताकि fibonacci अनुक्रम में n: th संख्या की गणना करने के लिए एक फ़ंक्शन को कार्यान्वित किया जा सके। फंक्शन ओ (एन) समय जटिलता देने के लिए संचय (सही अनुवाद नहीं हो सकता है) का उपयोग करके इसे 'उप-असाइनमेंट' लागू करना था। जब तक मैंने फ़ंक्शन (इंट -> इंटीजर) बनाने की कोशिश नहीं की, तब तक यह सब ठीक काम किया। थोड़ा प्रयोग करके मुझे एहसास हुआ कि वास्तव में बड़ी संख्या के लिए समय जटिलता ओ (एन^2) के करीब थी। यह मेरे लिए होता है कि यह इंटीजर कार्यान्वयन के कारण होना चाहिए, जो मुझे यह कैसे काम करता है इसके बारे में थोड़ा उत्सुक बनाता है। मैंने कुछ Google खोज की और मुझे कुछ भी उपयोगी नहीं मिला, इसलिए मैं आपको लोगों को स्पष्टीकरण या एक लिंक प्राप्त करने की आशा में बदल रहा हूं जो इसे पूरी तरह से समझाता है।

मेरे कोड:

ackfib 0 = 0 
ackfib 1 = 1   
ackfib n = loop n 1 0 1 
    where 
     loop n n1 n2 i 
      | i < n  = loop n (n1+n2) n1 (i+1) 
      | i == n = n1 
      | i > n  = error "n must be greater than or equal to 0" 

मैं सभी के लिए आभारी हूँ उत्तर देता

विक्टर

Answer 1

यह वास्तव में हास्केल के साथ कोई संबंध नहीं है, यह सिर्फ तथ्य यह है कि फिबोनैकी संख्या बढ़ने का एक परिणाम है तेजी से जल्दी। विशेष रूप से, nth Fibonacci संख्या के बारे में है (लॉग φ) एन या लगभग 0.48 एन बिट्स जहां φ सुनहरा अनुपात (1 + वर्ग 5)/2. है। के-बिट पूर्णांक के अतिरिक्त ओ (के) समय लेता है, आपके ओ (एन) परिवर्धन वास्तव में कुल ओ (एन^2) समय लेते हैं, क्योंकि औसतन आपके द्वारा जोड़े जाने वाले नंबरों में ओ (एन) बिट्स होते हैं।

(sticklers के लिए नोट:। बड़ी हे वास्तव में ऊपर में बड़ा थीटा होना चाहिए)

Answer 2

Reid's answer को जोड़ने के लिए, तथ्य यह है अपने एल्गोरिथ्म हे (एन) समय जटिलता है कि आप क्या करने पर विचार पर निर्भर करता है निष्पादन का कदम। यह समय जटिलता की एक आम गलतफहमी है: उस समय जटिलता हमेशा निष्पादन समय के अनुरूप होती है।

चरण पर विचार करने के लिए इस बात पर निर्भर करता है कि हम इस मुद्दे का विश्लेषण कैसे करना चाहते हैं। यदि आप एक चरण को इंटीजर के एक जोड़े के रूप में परिभाषित करते हैं, तो हाँ, आपके एल्गोरिदम संचयक के साथ ओ (एन) समय में चलता है। यदि आप एक शब्द अतिरिक्त (32- या 64-बिट अतिरिक्त) के रूप में एक चरण को परिभाषित करते हैं, तो यह ओ (एन^2) में चलाता है जैसा कि रीड समझाया गया है।

यदि आप अपने जटिलता विश्लेषण को निष्पादन समय के अनुरूप करना चाहते हैं तो आपको निष्पादन के एक चरण का उपयोग करने की आवश्यकता है जिसका निष्पादन समय निरंतर स्थिरता से ऊपर है, जैसे दो प्रोसेसर शब्दों के अतिरिक्त। इंटीग्रियों का जोड़ नहीं है, क्योंकि इंटीग्रेट्स मनमाने ढंग से बड़े हो सकते हैं।