जावा - चर के साथ अंतरिक्ष जटिलता - जावा, अंतरिक्ष-जटिलता

क्या अंतरिक्ष जटिलता O (n) है? चूंकि यदि k 5 से बढ़ता है, तो मेरा चर p भी 5 से बढ़ जाएगा।

यह सब तरीका अभी नोड को k पर मिलता है। उदाहरण के लिए: 1-> 5-> 3, जब k = 2, नोड 5 है।

public ListNode reverseKGroup(ListNode head, int k) {
int p = 1;

while (p < k) {
if (head.next == null) {
return head;
}
head = head.next;
p++;
}

return head
}

उत्तर:

सख्ती से आपके एल्गोरिथ्म पर विचार करते हुए, इसमें एक अंतरिक्ष जटिलता ओ (1) है। आपका इनपुट किसी सूची और संख्या का हेडर है k, लेकिन आपके अहंकार को किसी संदर्भ से अधिक जगह का उपभोग नहीं करना चाहिए head और एक संख्या p। मेरी राय में, मौजूदा सूची doesn "t आपके तरीके की जटिलता से संबंधित है। हालांकि, आपकी समय जटिलता O (N) है।

--- टिप्पणी में थियो के सवाल का जवाब:

p एक संख्या है (आदिम प्रकार इंट के इस मामले में, इसलिए यह 4 बाइट्स - निरंतर आकार लेता है)। अगर p बढ़ जाती है, इसका मतलब यह नहीं है कि यह अधिक जगह ले,लेकिन यह एक उच्च संख्या में संग्रहीत है। p = 5 का अर्थ है बाइट्स सेट करना: "0,0,0,5", p = 257 के लिए, बाइट सेट हैं: "0,0,1,2"। मुझे लगता है, जेवीएम बड़े एंडियन बाइट ऑर्डर में तारीख को स्टोर करता है, इसलिए पहले शून्य के बड़े बाइट्स का प्रतिनिधित्व करते हैं। छोटे एंडियन के साथ, बाइट ऑर्डर उलट हो जाएगा।

बेशक, आप सही हैं, कि बहुत बड़े के लिए N, 32 बिट लंबा पूर्णांक पर्याप्त नहीं है। इसलिए, इस तथ्य पर कड़ाई से विचार करते हुए, संख्याओं को स्टोर करने के लिए O (लॉग (N)) बिट आवश्यक हैं N। जैसे नंबर 2 ^ 186 को 187 बिट्स स्टोर करने की जरूरत है (एक 1 और 186 शून्य)

लेकिन वास्तव में, जब "सामान्य" डेटा के साथ काम करते हैं, तो आप इतनी बड़ी राशि की उम्मीद नहीं करते हैं। चूंकि केवल 32 बिट रजिस्टर (एक) से अधिक है int संख्या), आपको अगले संदर्भ के लिए 2 ^ 32 डेटा प्रविष्टियाँ (1 प्रविष्टि = 4 बाइट्स) चाहिए, कम से कम 4 बाइट्स मान Object संदर्भ, और वस्तु का आकार = कम से कम8 बाइट्स), वह 2 ^ 35 बाइट्स = 32 गीगाबाइट है। इसलिए, जब एक संख्या का उपयोग किया जाता है, तो यह आमतौर पर एक निरंतर अंतरिक्ष जटिलता माना जाता है। यह कार्य और परिस्थितियों पर निर्भर करता है।

इस बात पर निर्भर करता है कि आप पहले से मौजूद हैंसंरचना आपके अंतरिक्ष जटिलता का हिस्सा है, अंतरिक्ष जटिलता या तो ओ (1) या ओ (एन) है जहां एन सूची में संचालित होने की लंबाई है क्योंकि आप कोई नया नोड नहीं जोड़ते हैं और केवल मौजूदा नोड्स का संदर्भ देते हैं।

k केवल समय की जटिलता के लिए मायने रखता है।

इस एल्गोरिथ्म का उपयोग करने वाला एकमात्र स्थान है int p, जो इनपुट की परवाह किए बिना निरंतर है, इसलिए अंतरिक्ष जटिलता ओ (1) है। समय जटिलता वास्तव में हे (एन) है।