ठीक है कुछ इनपुट आकार के लिए रैखिक गहराई रैखिक आनुपातिक है?

Question

जब जावा (या उस मामले के लिए कोई अन्य प्रक्रियात्मक भाषा) में प्रोग्रामिंग करते हैं, तो मैं अक्सर को बनाम को हल करने के दौरान इसे हल करने के बीच चुनता हूं। रिकर्सिव विकल्प अक्सर एक पुनरावर्तक समाधान से अधिक सुरुचिपूर्ण होता है, इसलिए मैं आमतौर पर रिकर्सिव समाधान के लिए जाता हूं। एक अपवाद के साथ:

ढेर के बारे में चिंता मैं पुनरावर्ती समाधान से बचने के लिए अगर अधिकतम ढेर गहराई रैखिक इनपुट (या बुरा) के आकार के लिए आनुपातिक है करते हैं overflows। मुझे एहसास है कि कई अन्य भाषाओं में (स्कैला और क्लोजर जैसे जेवीएम को लक्षित करने वाले भी) कई एल्गोरिदम, उदाहरण के लिए मूल सूची एल्गोरिदम, अक्सर बार-बार व्यक्त किए जाते हैं जहां अधिकतम स्टैक गहराई सूची की लंबाई के समान होती है। ⁽¹⁾ तो, रैखिक-स्टैक-गहराई-एल्गोरिदम में स्टैक ओवरफ़्लो के बारे में मेरी चिंताएं उचित हैं?

टीएल; डीआर: क्या "स्टैक गहराई जटिलता" उचित मानी जाती है? लघुगणक जटिलता, उदाहरण के लिए पुनरावर्ती द्विआधारी खोज, हे (लॉग एन) निश्चित रूप से ठीक है, लेकिन के बारे में कैसे हे (एन), हे (एन लॉग ऑन एन), हे (एन)? आप आम तौर पर रेखा को कहां आकर्षित करेंगे? ⁽²⁾

^{(1) मुझे लगता है कि ऐसी भाषाओं कभी कभी @tailrec जैसी चीजों का समर्थन करता है, लेकिन इस सवाल जावा, सी # चिंताओं आदि
(2) ध्यान दें कि मैं सीपीयू भूमि के ऊपर के बारे में चिंतित नहीं हूँ आदि बस ढेर गहराई।}

Answer 1

आप यह पूछने के बिना इसका जवाब नहीं दे सकते कि आप किस आकार इनपुट का समर्थन करने में सक्षम होना चाहते हैं।

स्टैक पर रैखिक अंतरिक्ष जटिलता बिल्कुल ठीक है अगर आप कार्ड खेलने के डेक को संसाधित कर रहे हैं, और शायद आप पूरी तरह निराशाजनक हैं यदि आप बड़ी टेक्स्ट फाइलें ले रहे हैं। आपको यह सुनिश्चित करने की ज़रूरत है कि आपके आवेदन के लिए अधिकतम इनपुट आकार क्या होगा, या इसके बजाय, सबसे बड़ा इनपुट जिसके लिए आपको यह असफल नहीं लगता है।

हम यह हर समय करते हैं। उदाहरण के लिए, जब भी आप जावा में एक सरणी घोषित करते हैं, तो आप जानते हैं कि सरणी में 2 तत्व नहीं हो सकते हैं। क्या वो वजह बन रही हे? क्या इसका मतलब है कि कार्यक्रम टूटा हुआ है? शायद ऩही; लेकिन कभी-कभी ऐसा होता है, अगर भारी इनपुट कुछ ऐसा है जो आप सौदा करने में सक्षम होना चाहते हैं।

इसलिए मुझे नहीं लगता कि आप इसके बारे में भी बहुत अनुवादात्मक हो सकते हैं।अगर आपसे पूछा गया कि (सामान्य शब्दों में) किस समय जटिलता ठीक थी तो आप क्या कहेंगे? आप कुछ सामान्य सिद्धांत कह सकते हैं: आम तौर पर रैखिक ठीक है, आमतौर पर घातीय खराब होता है ... लेकिन असली जवाब यह है कि यह निर्भर करता है कि आप क्या कर रहे हैं।

Answer 2

ढेर गहराई जटिलता पर विचार करना एक बात है, लेकिन दूसरी बात इनपुट आकार ही है।

समस्या अपने डोमेन के बड़े इनपुट शामिल नहीं हैं (के लिए बढ़ाया विकास की प्रक्रिया में अवधि समय), तो हम पुनरावर्ती समाधान के लिए जा सकते हैं (बेशक, पुनरावर्ती समाधान के साथ ढेर की क्षमता से अधिक नहीं होना चाहिए सबसे बड़ा संभव इनपुट)।

यदि इनपुट आकार परिभाषित नहीं किया गया है, तो ओ (1) स्टैक गहराई या ओ (लॉग एन) स्टैक गहराई स्वीकार्य है, IMHO। यह संभव हो सकता है कि ओ (लॉग एन) स्वीकार्य नहीं हो सकता है यदि इनपुट आकार पर व्यावहारिक ऊपरी सीमा खगोलीय रूप से बड़ी है कि यह ढेर क्षमता से अधिक है। हालांकि, मुझे लगता है कि ऐसा मामला काफी दुर्लभ होगा।