एल्गोरिदम जटिलता: पैरामीटर के रूप में "बिजली खपत" कैसे देखें?

Question

अंतरिक्ष और समय को एल्गोरिदम की जटिलता का विश्लेषण करने के बैरोमीटर के रूप में माना जाता है। लेकिन इन दिनों मोबाइल उपकरणों पर जीपीयू की उपस्थिति के साथ, कई संभावित अनुप्रयोग हैं जो मोबाइल डिवाइस पर जटिल एल्गोरिदम चलाने के लिए उच्च प्रदर्शन का उपयोग कर सकते हैं। उदाहरण के लिए: आईपीओ के धातु ढांचे का उपयोग जीपीजीपीयू संचालन के लिए किया जा सकता है। लेकिन कहने की जरूरत नहीं है कि यह बहुत सारी शक्ति का उपभोग करता है। तो, मेरा सवाल यह है कि, यदि मैं एक मोबाइल डिवाइस पर एक ग्राफ खोज एल्गोरिदम विकसित/कार्यान्वित कर रहा हूं, तो क्या मुझे स्पेस-टाइम के साथ अपने एल्गोरिदम की "शक्ति" जटिलता पर भी विचार नहीं करना चाहिए? अब, मुझे पता है कि तर्क यह हो सकता है कि शक्ति कुछ ऐसा है जो एल्गोरिदम स्वयं का उपभोग नहीं करता है और मैं इसके साथ पूरी तरह से सहमत हूं। तो, शायद यहां मेरा व्याकरण यह कहने में गलत है कि शक्ति एक एल्गोरिदम की दक्षता को मापने का एक और आयाम है। लेकिन शक्ति को एल्गोरिदम के प्रदर्शन उपाय के रूप में नहीं देखा जाना चाहिए?

Answer 1

यह संभव होने के लिए, आपको ऊर्जा खपत का एक मॉडल चाहिए जो आप अपने एल्गोरिदम में परमाणु संचालन से संबंधित हो सकते हैं।

"एक गुणा ऊर्जा की एक इकाई का उपभोग करता है" और "एक स्मृति स्लॉट समय की प्रति इकाई ऊर्जा की दो इकाइयों का उपयोग करता है"। शायद संबंध ऊर्जा = समय एक्स अंतरिक्ष समझ में आ सकता है।

वैसे भी, इस तरह के "भद्दा" मॉडल को समय जटिलता के मॉडल के रूप में एक ही घटना का सामना करना पड़ सकता है: यह आधुनिक वास्तुकला के व्यवहार के साथ समानता नहीं लेता है और परिमाण के आदेशों से गलत हो सकता है।

अधिक सटीक मॉडल का उपयोग करना विश्लेषणात्मक रूप से अव्यवहारिक होगा।

Answer 2

सं। जटिलता बताती है कि एल्गोरिदम समय/स्मृति में कैसे स्केल करता है। बिजली समय और स्मृति का एक कार्य होगा।

कहें कि आपके पास एल्गोरिदम ए - ओ (एन^2) और बी - ओ (एन^3) है और वे दोनों एक ही समस्या को हल करते हैं। एन = 1000 बी के लिए बिजली का 1 यूनिट का उपयोग करता है जबकि ए 20 का उपयोग करता है। अब जब आप इसे एन = 10 के बी तक स्केल करते हैं तो आपको बिजली की 1000 इकाइयों की आवश्यकता होगी जबकि ए को केवल 2000 की आवश्यकता होगी। एन = 100 के बी को 1'000 ' 000 जबकि ए 200'000 की आवश्यकता होगी। और इसी तरह। यह मानता है कि एल्गोरिदम के निष्पादन के लिए ऊर्जा खपत स्थिर है।

वैसे ही वही बात समय के साथ होती है। उदाहरण के लिए लघु सरणी के लिए कुछ भी रैखिक खोज धड़कता है।

एक विशिष्ट मामले (निश्चित रिज़ॉल्यूशन पर यूआई प्रस्तुत करना) के लिए यह बिजली के उपयोग को मापने और इसे अनुकूलित करने के लिए समझ में आता है। लेकिन आज संकल्प के लिए क्या काम करता है कल कल सही बात नहीं होगी।