मुझे समझाइए कि आप किसी कोड की टाइम और स्पेस कॉम्प्लेक्सिटी कैसे निकालेंगे।

पहले यह देखिए कि इनपुट बढ़ने पर रनटाइम कैसे बढ़ता है, फिर constants और छोटे टर्म हटा दीजिए। कोड की बनावट पढ़िए: एक के बाद एक चलने वाले ब्लॉक जुड़ते हैं, nested loops गुणा होते हैं, और recursive calls अपनी recurrence के हिसाब से चलती हैं। स्पेस वह अतिरिक्त मेमोरी है जो आप इनपुट के अलावा लेते हैं, जिसमें call stack भी शामिल है। डिफॉल्ट रूप से worst case बताइए, और average case अलग से बताइए अगर दोनों में सच में फर्क हो।

मैं सबसे पहले n तय करता हूं, क्योंकि ऐसी बातचीत में आधी उलझन इसी से आती है कि दो लोग अलग अलग चीजें नाप रहे होते हैं। उसके बाद मैं कोड को बनावट के हिसाब से पढ़ता हूं। क्रम में चलने वाले ब्लॉक जुड़ते हैं, तो सबसे बड़ा वाला जीतता है; nested loops गुणा होते हैं; और recursive call एक recurrence बन जाती है जिसे मैं या तो खोल सकता हूं या पहचान सकता हूं। स्पेस के लिए मैं वह सब गिनता हूं जो इनपुट के अलावा allocate होता है, और call stack हमेशा शामिल करता हूं, जिसे recursion में लोग अक्सर भूल जाते हैं। एक ठोस उदाहरण: मेरे पास एक फंक्शन था जो linear लग रहा था क्योंकि वह orders की एक list पर सिर्फ एक loop था, लेकिन उसके अंदर हम एक helper बुला रहे थे जो list में id से record ढूंढता था। वह lookup linear थी, तो असली लागत quadratic निकली, और यह तभी सामने आई जब एक कस्टमर के करीब चालीस हजार orders हो गए। हमने list की जगह id वाली dictionary रख दी और endpoint लगभग नौ सेकंड से घटकर दो सौ मिलीसेकंड के अंदर आ गया। तो मेरा नियम यही है कि हर call के अंदर झांको, सिर्फ दिखने वाले loops तक मत रुको।