मुझे अपने एल्गोरिदम की जटिलता को निर्धारित करने में समस्या है क्योंकि यह ES6 की विशेषताओं का उपयोग करता है और निश्चित रूप से वे जंजीर विधियां हैं। मैं पहले से ही उन तरीकों की कुछ बुनियादी जटिलताओं को जानता हूं, उदाहरण के लिए Array.prototype.map की जटिलता O(n) है। लेकिन जब हम किसी एल्गोरिथम की जटिलता का निर्धारण करना चाहते हैं, तो हम जंजीर विधि का प्रबंधन कैसे करते हैं?

उदाहरण के लिए, मान लें कि हमारे पास एक फ़ंक्शन है जो एक सरणी के लिए अपनी सकारात्मक संख्याओं का योग देता है

let sumPositive = arr => arr.filter(i => i > 0).reduce((a, b) => a + b, 0);

console.log(sumPositive([1, 2, 3, -4])); // 6
console.log(sumPositive([1, 2, 3, 4])); // 10

इसलिए, उस फ़ंक्शन की जटिलता क्या है?

एक अन्य उदाहरण यह एल्गोरिथम है जो किसी दिए गए स्ट्रिंग के लिए, स्ट्रिंग में प्रत्येक वर्ण की गणना लौटाता है

let charCount = str =>  str.split('').map(
  (c,_,str) => str.filter(i => i===c)
  ).reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

console.log(charCount("hi")); // {"h": 1, "i": 1}

console.log(charCount("hello to you")); // {"h": 1, "e": 1, "l": 2, "o": 3, " ": 2, "t": 1, "y": 1, "u": 1}

तो इस सेकंड के लिए मुझे विशेष रूप से इसकी जटिलता को जानने की जरूरत है क्योंकि हम नेस्टेड विधि जैसे फ़िल्टर को मैप के अंदर कॉल किया जा रहा है के साथ काम कर रहे हैं।

तो ऐसे एल्गोरिदम की जटिलता को निर्धारित करने के लिए किसी भी सामान्य विधि का स्वागत है।

ध्यान दें: इस प्रश्न में सभी जटिलता समय-जटिलता है स्थान नहीं

धन्यवाद

0
Patrissol Kenfack 18 जिंदा 2020, 15:21

2 जवाब

सबसे बढ़िया उत्तर

जंजीर के तरीके वास्तव में सिर्फ सुविधा के लिए हैं। map() या filter() एक सरणी देता है। अब आप पहले ऐरे पर एक नाम डाल सकते हैं, जैसे let result = arr.map(...) और फिर उस result ऐरे पर अन्य चीजें कर सकते हैं, या आप सीधे द्वारा लौटाए गए ऐरे पर कुछ कर सकते हैं। map() (या filter()), जैसे map().filter().<more chaining if you want>

तो, यह अनुक्रमिक निष्पादन के बराबर है। इस उदाहरण पर विचार करें,

let sumPositive = arr => arr.filter(i => i > 0)
                            .reduce((a, b) => a + b, 0);

let arr = [1, 2, 3, -4];

let filteredArray = arr.filter(i => i > 0); // O(n)
let reducedResult = filteredArray.reduce((a, b) => a + b, 0); // O(n)

console.log(sumPositive(arr)); // 6
console.log(reducedResult) // 6

अब आप देखते हैं कि filter() O(n) लेता है और फिर reduce() O(n) लेता है, इसलिए आपको अंतिम समय जटिलता के रूप में O(n) + O(n) ==> O(n) मिलता है।

मुझे आशा है कि आप इसी तरह दूसरे उदाहरण के लिए जटिलता पा सकते हैं। अगर आपको सहायता चाहिए तो मुझे टिप्पणियों में बताएं।

3
Ajay Dabas 18 जिंदा 2020, 15:49

@ अजय डबास ने आपके प्रश्न का उत्तर दिया; मैं आपके प्रश्न का उत्तर टिप्पणियों में दे रहा हूँ:

तो क्या आप मुझे एक उदाहरण दे सकते हैं कि मैं कोड या कुछ उपयोगी लिंक को बेहतर बनाने के लिए क्या कर सकता हूं?

आपका पहला उदाहरण कोई आसान नहीं होने वाला है, लेकिन आप अपने दूसरे एल्गोरिदम की समय जटिलता को कम कर सकते हैं:

let charCount = str =>  str.split('')
  .map((c,_,str) => str.filter(i => i===c))
  .reduce((a, b) => a.hasOwnProperty(b[0]) ? a : ({...a, [b[0]]: b.length}), {});

आप filter() पद्धति का उपयोग न करके ऐसा कर सकते हैं। ऐसा करने की कोई आवश्यकता नहीं है यदि आप सभी कुंजियों और उनकी वर्तमान गणनाओं की अनुक्रमणिका बनाए रखते हैं .. और आप पहले से ही reduce() के साथ ऐसा कर रहे हैं:

    let charCount = str => 
        return str.split('').reduce(
            (acc, nextChar) => {
                return {
                    ...acc,
                    [nextChar]: (acc[nextChar] || 0) + 1
                };
            },
            Object.create(null)
        );
    };

यह O(n) होना चाहिए - हम केवल दो बार सरणी को पुनरावृत्त करते हैं। ध्यान दें कि कैसे हमें filter() परिणामों की आवश्यकता नहीं है क्योंकि हमें बस इतना करना है कि संचायक में उस वर्ण के लिए मौजूदा गणना करें और इसे एक से बढ़ा दें।

Object.create(null) का उपयोग null प्रोटोटाइप के साथ एक नई वस्तु बनाना है - इसका मतलब है कि हमें hasOwnProperty() का उपयोग करने की आवश्यकता नहीं है।

आपको यह ध्यान रखना चाहिए कि सिर्फ इसलिए कि कुछ O(n^2) है, इसका मतलब यह नहीं है कि कोई प्रदर्शन समस्या है। बिग ओ नोटेशन सिर्फ यह बताता है कि इनपुट डेटा बढ़ने पर कुछ कोड कैसे व्यवहार करेंगे। कोड को ऑप्टिमाइज़ करने के लिए केवल तभी देखें जब आपको पता हो कि यह एक समस्या है।

1
Dan 18 जिंदा 2020, 16:34