मैंने समय पुस्तकालय का उपयोग किया है और कितने समय के लिए समय दिया हैपुनरावर्ती एल्गोरिथ्म 50 तक की फ़ाइब संख्याओं की गणना करने के लिए लेता है। उन नंबरों को दें, क्या कोई सूत्र है जो मैं यह निर्धारित करने के लिए उपयोग कर सकता हूं कि संभावित रूप से फ़ाइबर (100) की गणना करने में कितना समय लगेगा?
छोटे मूल्यों के लिए टाइम्स:
Fib(40): 0.316 sec
Fib(80): 2.3 years
Fib(100): ???
उत्तर:
उत्तर № 1 के लिए 1यह उपयोग में एल्गोरिथ्म पर बहुत निर्भर करता है। प्रत्यक्ष गणना में निरंतर समय लगता है। संस्मरण के बिना पुनरावर्ती अभिकलन घातांक है, फी का एक आधार है। इसमें संस्मरण जोड़ें, और यह लघुगणक के समय तक चला जाता है।
केवल वही जो आपके डेटा को फिट कर सकता है वह है घातीय समय। बुनियादी गणित कर रहा है ...
(2.3 years / 0.316 sec) ** (1.0/40)
gives us
base = 1.6181589...
जी, वह देखो! 10 ^ 4 से एक भाग कम, फी से अधिक 4!
बता दें कि t (n) Fib (n) की गणना करने का समय है। हम उस परिकल्पना का समर्थन कर सकते हैं
t(n) = phi * t(n-1)
Therefore,
t(100) = phi^(100-80) * t(80)
मुझे भरोसा है कि आप यहां से खत्म कर सकते हैं।