जावास्क्रिप्ट एल्गोरिदम: फाइबोनैचि अनुक्रम को हल करें (लीटकोड)

फाइबोनैचि संख्याएंF(n) , जिन्हें आमतौर पर एक अनुक्रम के रूप में दर्शाया जाता है, फाइबोनैचि अनुक्रम कहा जाता है , जैसे कि प्रत्येक संख्या 0और से शुरू होने वाली दो पिछली संख्याओं का योग है 1। निम्नलिखित पूर्णांक अनुक्रम में संख्याएँ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

वह है

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

उदाहरण 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

इस समस्या को हल करने के लिए कई विकल्प हैं: पुनरावर्तन दृष्टिकोण।

पुनरावर्तन दृष्टिकोण

एक सरल विधि जो प्रत्यक्ष पुनरावर्ती कार्यान्वयन गणितीय पुनरावर्तन संबंध है। इस समस्या को हल करने का सबसे धीमा तरीका क्योंकि इसमें घातीय समय जटिलता : O(2^N) और अंतरिक्ष जटिलता : O(N) लगती है ।

मेमोइज़ेशन (टॉप डाउन अप्रोच) का उपयोग करते हुए डायनेमिक प्रोग्रामिंग

अब तक परिकलित फाइबोनैचि संख्याओं को संचित करके हम पुनरावर्ती में किए गए बार-बार किए गए कार्य से बच सकते हैं। हमें केवल मानचित्र में सभी मानों को संग्रहित करने की आवश्यकता है। समय जटिलता : O(N) और स्थान जटिलता : O(N) ।

पुनरावृत्ति दृष्टिकोण

पुनरावृत्ति, सभी उप-समस्याओं को हल करने और पहले से ही गणना किए गए फाइबोनैचि मानों का उपयोग करके N तत्व के लिए उत्तर वापस करने के साथ। समय जटिलता : O(N) और अंतरिक्ष जटिलता : O(N) ।

पुनरावृति दृष्टिकोण ( अंतरिक्ष अनुकूलित)

हम पिछले दो नंबरों को संग्रहीत करने वाले पुनरावृति दृष्टिकोण को केवल इसलिए अनुकूलित कर सकते हैं क्योंकि श्रृंखला में अगला फिबोनाची नंबर प्राप्त करने के लिए हमें बस इतना ही चाहिए। समय जटिलता : O(N) और अंतरिक्ष जटिलता : O(1) ।

मैट्रिक्स घातांक दृष्टिकोण

परिणामी मैट्रिक्स में तत्व (0, 0) से फाइबोनैचि संख्या प्राप्त करने के लिए मैट्रिक्स घातांक का उपयोग करें । ऐसा करने के लिए हम फिबोनैचि अनुक्रम के लिए मैट्रिक्स समीकरण पर भरोसा कर सकते हैं, एन-वें फाइबोनैचि संख्या को खोजने के लिए:

यह फॉर्मूला कैसे काम करता है आप विकी पर देख सकते हैं

इस समाधान में है: समय जटिलता : O(logN) और अंतरिक्ष जटिलता : O(logN) ।

गणित दृष्टिकोण

हम इसका उपयोग कर सकते हैं golden ratio forumula:

फाइबोनैचि अनुक्रम और सुनहरा अनुपात कैसे काम करता है, इसके बारे में और जानने के लिए यहां एक लिंक दिया गया है।

इस समाधान में है: समय जटिलता : O(logN) और अंतरिक्ष जटिलता : O(1) ।

इसके अलावा, कभी-कभी किसी दिए गए एन के लिए मान नहीं लौटाना आवश्यक होता है, लेकिन किसी दिए गए एन तक फाइबोनैचि तत्वों की एक सरणी वापस करने के लिए।

उदाहरण:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

और डायनेमिक प्रोग्रामिंग मेमोइज़ेशन का उपयोग करके थोड़े से बदलाव के साथ:

हमने फाइबोनैचि समस्या को हल करने के लिए अलग-अलग विकल्पों पर विचार किया है, समझने में सबसे कठिन मैट्रिक्स एक्सपोनेंटिएशन है, लेकिन आमतौर पर पिछले 4 तरीकों का ज्ञान एक साक्षात्कार के लिए पर्याप्त है।

आशा है कि यह आपके लिए उपयोगी था!

पढ़ने के लिए धन्यवाद! जल्दी मिलते हैं।

PlainEnglish.io पर अधिक सामग्री । हमारे मुफ़्त साप्ताहिक न्यूज़लेटर के लिए साइन अप करें । ट्विटर , लिंक्डइन , यूट्यूब और डिस्कॉर्ड पर हमें फॉलो करें । ग्रोथ हैकिंग में रुचि रखते हैं? सर्किट देखें ।