पेड़ के ट्रैवर्सल की समय जटिलता क्या है?

पेड़ ट्रैवर्सल की समय जटिलता क्या है, मुझे यकीन है कि यह स्पष्ट होना चाहिए लेकिन मेरा गरीब मस्तिष्क अभी इसे बाहर नहीं कर सकता है।पेड़ के ट्रैवर्सल की समय जटिलता क्या है?

स्रोत

2011-02-10 new299

यह रैखिक कला प्रोग्रामिंग वॉल्यूम 1 पृष्ठ 326 – new299

है क्या यह Knuth कंप्यूटर प्रोग्रामिंग की कला है? मैं इसे एक दोस्त को एक अच्छा उदाहरण देने के लिए यह खोजने की कोशिश कर रहा हूं कि एन-आरी पेड़ के लिए यह रैखिक है। – Nicholas

हां Knuth की "कंप्यूटर प्रोग्रामिंग की कला" – new299

यह निर्भर करता है कि आप किस तरह का ट्रैवर्सल कर रहे हैं और एल्गोरिदम, लेकिन आम तौर पर यह ओ (एन) होगा जहां एन पेड़ में नोड्स की कुल संख्या होगी। गहराई के पहले ट्रैवर्सल के कैननिकल रिकर्सिव कार्यान्वयन, गहरे स्तर के क्रम में स्मृति (ढेर पर) का उपभोग करेंगे, जो एक संतुलित पेड़ पर लॉग (एन) होगा।

स्रोत

2011-02-10 11:20:33 Uri

क्या यह एक एन-आरी पेड़ के सच है? मेरे पास एक डेटा संरचना है जो अधिकतम गहराई का पेड़ है और इसे पार करने के लिए मेरा दोस्त 3 लूप के लिए उपयोग कर रहा है, और कह रहा है कि उसका एल्गोरिदम 'ओ (एन^3)' समय में चलता है, लेकिन मेरा मानना है कि यह ' एन' समय, 'n' पेड़ – Nicholas

@ नोकोलस में नोड्स की कुल संख्या होने के नाते, आप सही हैं और आपका मित्र गलत है। यह चालू है)। – Uri

नहीं कि सिर्फ nn नोड्स के साथ एक पेड़ के लिए होगा?

आप प्रत्येक पेड़-छुट्टी पर जाते हैं, है ना? तो मैं कहूंगा कि यह रैखिक है।

स्रोत

2011-02-10 11:18:28 Nanne

मुझे लगता है कि यह "एन नोड्स" के साथ पेड़ होना चाहिए और "एन पत्ते" नहीं। – aamadmi

आप सही हैं, गलत टर्मिनोलिजी :) – Nanne

@Nanne सही एल्गोरिदम के साथ यह वास्तव में समय में एक रैखिक जटिलता है (प्रत्येक नोड पर जाकर), लेकिन इसमें अभी भी अंतरिक्ष में रैखिक जटिलता नहीं हो सकती है। ढेर का उपयोग करने की तरह। – Tim

पेड़ के ट्रैवर्सल की समय जटिलता क्या है?

उत्तर

संबंधित मुद्दे