checkIfBalanced() पर कोड बनाने पर अंतरिक्ष जटिलता नीचे दिए गए कोड में विधि सही होती है यदि पेड़ संतुलित है और अन्यथा गलत है। हालांकि प्रत्येक रिकर्सन में यह ट्रीडाटा ऑब्जेक्ट बनाता है। मेरी राय में अंतरिक्ष जटिलता ओ (1) है क्योंकि प्रत्येक स्टैक फ्रेम पॉप-अप होने के बाद, उस स्टैक फ्रेम पर बनाए गए ऑब्जेक्ट का संदर्भ खो जाता है और कचरा एकत्र होता है। क्या मैं सही हूँ?रिकर्सन
कृपया ध्यान दें:
मैं में सुधार/मेरे कोड को बदलने के लिए सुझाव के लिए नहीं देख रहा हूँ। कोड का निम्नलिखित उदाहरण मेरे प्रश्न पूछने के लिए तैयार है।
इसके अलावा,
please ignore space-complexity adding stack frames। मैं बनाई गई 'ट्रीडाटा' ऑब्जेक्ट्स की स्पेस जटिलता की तलाश में हूं। मुझे लगता है कि किसी भी समय केवल 3 वृक्षारोपण वस्तुएं होंगी। मैं क्या सत्यापित करना चाहता हूँ। धन्यवाद।
private static class TreeData {
private int height;
private boolean isBalanced;
TreeData(int height, boolean isBalanced) {
this.height = height;
this.isBalanced = isBalanced;
}
}
public boolean checkIfBalanced() {
if (root == null) {
throw new IllegalStateException();
}
return checkBalanced(root).isBalanced;
}
public TreeData checkBalanced(TreeNode node) {
if (node == null) return new TreeData(-1, true);
TreeData tdLeft = checkBalanced(node.left);
TreeData tdRight = checkBalanced(node.right);
if (tdLeft.isBalanced && tdRight.isBalanced && Math.abs(tdLeft.height - tdRight.height) <= 1) {
return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, true);
}
return new TreeData(Math.max(tdLeft.height, tdRight.height) + 1, false);
}
इसलिए स्मृति में ट्रीडाटा की ऑब्जेक्ट्स की संख्या केवल 1 होगी - इसलिए, यदि मैं "स्टैक स्पेस को अनदेखा करता हूं" , जटिलता ओ (1) होगी? यदि संदर्भ स्टैक से पॉप किए जाते हैं तो क्या वे वस्तुएं कचरा इकट्ठा होंगी? – JavaDeveloper
@ जावा डेवलपर- 1. यदि आप स्टैक स्पेस को अनदेखा करते हैं, और केवल वर्तमान संदर्भ पर विचार करते हैं, तो केवल 1 सक्रिय TreeData ऑब्जेक्ट होगा। 2. *** शायद/शायद नहीं ***, जैसे ही स्टैक सभी नोड्स को पॉप आउट करता है, ऑब्जेक्ट्स कचरा इकट्ठा हो सकता है या नहीं, यह अनुमान लगाने के लिए जेवीएम पर निर्भर करता है कि क्या उन्हें फिर से उपयोग किया जा रहा है या नहीं भविष्य। सच्चाई के लिए, आपको उन ऑब्जेक्ट्स को 'नल' पर सेट करके मैन्युअल रूप से ऐसा करने की ज़रूरत है ताकि वे कचरा इकट्ठा कर सकें। जवाब पढ़ें (विशेष रूप से स्टीफन सी का जवाब) -> http://stackoverflow.com/questions/27781116/garbage -collection में जावा-साथ पुनरावर्ती-समारोह –