लिस्प कार्यक्रमों के एल्गोरिदमिक विश्लेषण के लिए सुझाव?

Question

सामान्य लिस्प कार्यक्रमों में कौन से संचालन को पर्याप्त रूप से आदिम माना जाना चाहिए ताकि एल्गोरिदमिक विश्लेषण में एक "चरण" की गणना हो सके? उनके कार्यान्वयन में आधुनिक लिस्प्स कितनी व्यापक रूप से भिन्न होते हैं?

निश्चित रूप से छोटे पूर्णांक वाले अंकगणित एक ही चरण के रूप में गिना जाएगा, लेकिन बड़ी संख्या के बारे में क्या होगा? और reverse और nreverse के बीच अंतर पर विचार करने के बारे में क्या? विशेष रूप से, nreversereverse के थेटा है? सभी सरणी और अनुक्रम संचालन के बारे में क्या? इसके अलावा, मैक्रोज़ कैसे आते हैं - जटिलता का विश्लेषण करते समय मैक्रोज़ के बारे में मुझे कैसे सोचना चाहिए?

Answer 1

• वर्दी "सिंगल चरणों" की निचली परत खोजने की कोशिश न करें, बस पता करें कि ओ (1) क्या है और क्या नहीं है।
• "बड़ी संख्या" (bignum एस) का जोड़ ओ होना चाहिए (लॉग एन) जहां एन पूर्णांक का बड़ा है। गुणा के लिए कई अलग-अलग एल्गोरिदम हैं; मैं इस क्षेत्र में एक विशेषज्ञ नहीं हूं, और यह कार्यान्वयन विशिष्ट होने की संभावना है।
• reverse और nreverse दोनों को सीडीआर-इनपुट-एंड-कंस-आउटपुट रणनीति द्वारा ओ (एन) (reverse लागू किया जा सकता है; nreverse सीडीआरिंग के दौरान पॉइंटर्स का आदान-प्रदान करके)। अगर मैं अपरिचित शब्द "theta" सही ढंग से समझता हूं, तो हाँ। नोट, हालांकि, सीएल मानक समय जटिलता के बारे में कोई गारंटी नहीं देता है।
• बिल्ट-इन अनुक्रम ऑपरेशन आम तौर पर तर्क के प्रकार के आधार पर एक सरणी या सूची-विशिष्ट कार्यान्वयन चुनकर कार्यान्वित किए जाते हैं, और इसलिए उस डेटा प्रकार के लिए सामान्य कुशल एल्गोरिदम होने की अपेक्षा की जानी चाहिए।
• मैक्रोज़ केवल अन्य कोड में विस्तार करते हैं। आप उनके विस्तार को देख सकते हैं, या देख सकते हैं कि उन्हें क्या करने के लिए दस्तावेज किया गया है, या उनके विस्तार के उपयोग के एल्गोरिदम के बारे में एक शिक्षित अनुमान बनाते हैं। मैक्रोएक्सपेंडर की जटिलता पूरी तरह से अप्रासंगिक है (जब तक आप eval/compile का उपयोग नहीं कर रहे हैं, इस मामले में आपको कार्यान्वयन के कंपाइलर की जटिलता के बारे में भी सोचना होगा) क्योंकि यह एक बार संकलन समय पर चलता है; केवल विस्तारित कोड मायने रखता है।