मान लीजिए कि हमारे पास एन तत्वों का बाइनरी ढेर है और अन्य तत्वों को शामिल करना चाहते हैं (जरूरी नहीं कि एक के बाद एक)। इसके लिए कुल समय क्या होगा?एक तत्व बाइनरी ढेर में एन तत्वों को सम्मिलित करने की असीमित समय जटिलता पहले से ही एन तत्व
मुझे लगता है कि यह theta (n logn) है क्योंकि एक प्रविष्टि लॉगऑन लेती है।
मान लिया जाये कि हम दिए गए हैं:
की वर्तमान आकार पर हम निम्नलिखित है प्रविष्टि गुण:
तो
वर्स्टकेस तब होता है जब हम नए न्यूनतम मूल्य डालते हैं, इसलिए अप-ढेर को पूरी शाखा यात्रा करना पड़ता है।
बेस्टकेस तब होता है जब न्यूनतम-ढेर (शीर्ष पर न्यूनतम के साथ ढेर) हम बिग (अद्यतन शाखा पर सबसे बड़ी) मूल्य डालते हैं (इसलिए अप-हीप तुरंत बंद हो जाता है)।
आप पहले से ही n तत्वों से युक्त ढेर पर n संचालन की श्रृंखला के बारे में पूछा है, यह आकार बढ़ेगा है
from n to 2*n
क्या asymptotically है ...
n=Θ(n)
2*n=Θ(n)
क्या हमारे समीकरण सरल करता है। (हमें एन के विकास के बारे में चिंता करने की ज़रूरत नहीं है, क्योंकि इसकी वृद्धि लगातार कारक है)।
तो, हम आपरेशन के "n सम्मिलन के लिए" है:
पी.एस. थेटा Θ, ओमेगा Ω प्रतीकों को प्रदर्शित करने के लिए, आपको यूटीएफ -8 स्थापित/संगत होना चाहिए।
अपने theeta (nlogn) नहीं ... अपने आदेश (nlogn) सम्मिलन से कुछ के बाद से कम तो सटीक logn समय लग सकता है ... इसलिए n सम्मिलन के लिए लगेगा समय < = nlogn
= > समय जटिलता = ओ (nlogn)
दिया गया: एन तत्वों का ढेर और एन तत्वों को सम्मिलित किया जाना चाहिए। तो अंत में 2 * एन तत्व होंगे। चूंकि ढेर 2 तरीकों से बनाया जा सकता है 1. लगातार सम्मिलन और 2. ढेर विधि बनाएं। Amoung इन बिल्ड ढेर विधि को हेप बनाने के लिए ओ (एन) समय लगता है जिसे How can building a heap be O(n) time complexity? में समझाया गया है। तो कुल समय आवश्यक ओ (2 * एन) है जो ओ (एन)
जैसा लगता है कि मौजूदा ढेर का आकार किसी भी तरह परिणाम में प्रवेश करना चाहिए। –