अनंतस्पर्शी जटिलता, पुनरावृत्तियाँ, खोज, वर्गीकरण व हैशिंग

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

1. पुनरावृत्ति T(n) = 3T(n/2) + n हल होकर बनती है:

   1. Θ(n log n)
   2. Θ(n^log₂3)
   3. Θ(n)
   4. Θ(n²)
   उत्तर देखें

   उत्तर: B — Θ(n^{log₂3})

   यहाँ a = 3 व b = 2, अतः n^{log_b a} = n^log₂3 ≈ n^1.585, जो शीर्ष स्तर के f(n) = n से तेज़ बढ़ता है — अतः पत्तियाँ प्रभावी हैं और उत्तर Θ(n^log₂3) है। विकल्प A वह उत्तर है जब दोनों तुलनीय हों, जैसे T(n) = 2T(n/2) + n में। यह पुनरावृत्ति पहचानने योग्य इसलिए है कि वह काराचुबा गुणन है: भोले चार के बजाय तीन आधे-आकार गुणन, जो n² को n^1.585 बनाता है और कलनविधि का सम्पूर्ण अभिप्राय वही है।

2. T(1) = 1 सहित T(n) = T(n−1) + n हल होकर बनती है:

   1. Θ(n)
   2. Θ(n log n)
   3. Θ(n²)
   4. Θ(log n)
   उत्तर देखें

   उत्तर: C — Θ(n²)

   खोलने पर n + (n−1) + … + 1 = n(n+1)/2 = Θ(n²) मिलता है। मास्टर प्रमेय लागू नहीं होता: उसे n/b आकार की उप-समस्या चाहिए, अचर भाग, जबकि यह अचर मात्रा से घटाता है, जिससे पुनरावर्तन log n के बजाय n गहरा हो जाता है। वही भेद सम्पूर्ण प्रश्न है। वह व्यावहारिक रूप से भी महत्वपूर्ण है — ठीक यही पुनरावृत्ति क्विकसॉर्ट देता है जब प्रत्येक पिवट शेष में सबसे छोटा अवयव हो, जो पहले से वर्गीकृत निवेश प्रथम-अवयव पिवट के साथ करता है, n = 100 हेतु 4950 तुलनाएँ देते हुए।

3. 100 भिन्न संख्याओं का अधिकतम व न्यूनतम दोनों ढूँढ़ने हेतु आवश्यक तुलनाओं की न्यूनतम संख्या क्या है?

   संख्यात्मक उत्तर — मान टाइप करें।

   उत्तर देखें

   उत्तर: 148

   ⌈3n/2⌉ − 2 = 150 − 2 = 148। विधि युग्मन है: 100 संख्याओं की तुलना 50 जोड़ों में करें (50 तुलनाएँ), फिर 50 विजेताओं को चालू अधिकतम से (49) व 50 पराजितों को चालू न्यूनतम से (49) चलाएँ — कुल 148। भोला उत्तर 198, प्रत्येक n − 1 के दो स्वतंत्र अवलोकनों से आता है, और वह अधिक बुरी कलनविधि की सही गणना है, इसीलिए प्रश्न न्यूनतम पूछता है। यह परिबंध तंग है: कोई विधि इससे अच्छा नहीं करती, और यह जानना ही अभ्यर्थी को 148 को बहुत छोटा मानकर पुनर्विचार करने से रोकता है।

4. 1000 अवयवों की वर्गीकृत सरणी पर द्विआधारी खोज निकृष्टतम स्थिति में कितनी तुलनाएँ करती है?

   1. 10
   2. 11
   3. 9
   4. 500
   उत्तर देखें

   उत्तर: A — 10

   निकृष्टतम स्थिति ⌈log₂(n + 1)⌉ = ⌈log₂1001⌉ = 10 है, क्योंकि प्रत्येक तुलना शेष परिसर आधा करती है और 2¹⁰ = 1024 ≥ 1001। विकल्प B, 1024 अवयवों का उत्तर है, जहाँ ⌈log₂1025⌉ = 11 — सरणी में एक अवयव का अंतर पूरी एक अतिरिक्त तुलना देते हुए, और जब प्रश्न दो की घात से ज़रा आगे का आकार चुनता है तो वह इसी का दोहन करता है। परिणाम एक सामान्य भ्रम भी तय करता है: सरणी दुगुनी करने से एक तुलना जुड़ती है, दुगुना काम नहीं।

5. निम्नलिखित में कौन वर्गीकरण कलनविधियाँ Θ(n log n) निकृष्टतम समय रखती हैं? (एक से अधिक सही हो सकते हैं।)

   1. मर्ज सॉर्ट
   2. क्विकसॉर्ट
   3. हीपसॉर्ट
   4. इंसर्शन सॉर्ट
   उत्तर देखें

   उत्तर: A — मर्ज सॉर्ट; C — हीपसॉर्ट

   मर्ज सॉर्ट व हीपसॉर्ट। दोनों निवेश चाहे कोई हो लघुगणकीय रूप से विभाजित या छनते हैं, अतः उनकी निकृष्टतम स्थिति उनके औसत से मिलती है। क्विकसॉर्ट निकृष्टतम स्थिति में Θ(n²) है — उसका O(n log n) पिवट-चुनावों पर औसत है, और वर्गीकृत निवेश पर बुरा पिवट-नियम ठीक द्विघात स्थिति पर पहुँचता है। इंसर्शन सॉर्ट भी Θ(n²) है, चाहे वह लगभग-वर्गीकृत निवेश पर Θ(n) हो, इसीलिए वह तेज़ वर्गीकरणों के भीतर आधार-स्थिति के रूप में प्रयुक्त होता है। साथ ले जाने योग्य विभेदक गुण यह है कि हीपसॉर्ट Θ(1) अतिरिक्त स्थान से Θ(n log n) प्राप्त करता है, जहाँ मर्ज सॉर्ट को Θ(n) चाहिए — ऐसी सूची के पीछे प्रायः वास्तविक प्रश्न वही होता है।

6. तुलना-वर्गीकरण हेतु Ω(n log n) निम्न परिबंध किससे निकलता है:

   1. सर्वज्ञात कलनविधि मर्ज सॉर्ट होने से
   2. निर्णय-वृक्ष को n! पत्तियाँ चाहिए होने से, अतः ऊँचाई कम-से-कम log₂(n!)
   3. n अवयवों की अदला-बदली की लागत से
   4. विभाजन-और-जीत की पुनरावर्तन गहराई से
   उत्तर देखें

   उत्तर: B — निर्णय-वृक्ष को n! पत्तियाँ चाहिए होने से, अतः ऊँचाई कम-से-कम log₂(n!)

   प्रत्येक तुलना-आधारित वर्गीकरण एक द्विआधारी निर्णय-वृक्ष है जिसकी पत्तियाँ संभव उत्तर हैं, और n! क्रम हैं — अतः वृक्ष को n! पत्तियाँ चाहिए और इसलिए ऊँचाई कम-से-कम log₂(n!) = स्टर्लिंग सन्निकटन से Θ(n log n)। वह समस्या के विषय में कथन है: वह प्रत्येक विद्यमान या भविष्य के तुलना-आधारित वर्गीकरण पर लागू है। विकल्प A निम्न परिबंध को ज्ञात कलनविधि से मिले उच्च परिबंध से भ्रमित करता है, और वही नामित करने योग्य वैचारिक त्रुटि है — इस प्रकार सिद्ध निम्न परिबंध अच्छी कलनविधि से नहीं हराया जा सकता, केवल मॉडल बदलकर, और ठीक वही काउंटिंग व मूलांक वर्गीकरण पूर्णतः तुलना न करके करते हैं।

7. काउंटिंग सॉर्ट Θ(n + k) में चलता है जहाँ k कुंजी-परिसर है। वह बुरा चुनाव है जब:

   1. n बड़ा हो
   2. k, n से बहुत बड़ा हो
   3. निवेश पहले से वर्गीकृत हो
   4. स्थायित्व आवश्यक हो
   उत्तर देखें

   उत्तर: B — k, n से बहुत बड़ा हो

   Θ(k) पद गणना-सरणी की लागत है, अतः सौ 32-बिट पूर्णांक वर्गीकृत करने का अर्थ है k ≈ 4 × 10⁹ और कलनविधि तुलना-आधारित वर्गीकरण से विनाशकारी रूप से बुरी — k ≫ n ठीक वही बुरी स्थिति है। विकल्प D उलटा है: काउंटिंग सॉर्ट स्थायी है, और वह उसकी विक्रय-विशेषताओं में एक है, इसीलिए मूलांक वर्गीकरण उस पर बना है। सामान्य शिक्षा यह है कि दो चर वाले परिबंध की तुलना दूसरे परिबंध से तभी हो सकती है जब उनके सापेक्ष आकार ज्ञात हों, और k देता प्रश्न आपको बता रहा है कि कौन-सा पद महत्वपूर्ण है।

8. शृंखलन सहित हैश तालिका m खानों में n कुंजियाँ रखती है। उसका निकृष्टतम खोज समय है:

   1. O(1)
   2. O(n)
   3. O(log n)
   4. O(n/m)
   उत्तर देखें

   उत्तर: B — O(n)

   O(n)। हैश फलन की परिभाषा में कुछ भी n कुंजियों में प्रत्येक को उसी खाने में हैश होने से नहीं रोकता, और तब खोज n लंबाई की शृंखला पर चलती है। विकल्प A समरूप-हैशिंग मान्यता में प्रत्याशित समय है, और विकल्प D औसत शृंखला-लंबाई α = n/m — दोनों औसत स्थिति के विषय में सत्य कथन, और कोई भी निकृष्टतम स्थिति नहीं। पाठ्यक्रम निकृष्टतम जटिलता पूछता है, अतः भेद पांडित्य नहीं: इसी कारण निकृष्टतम-संवेदी अनुप्रयोग O(1) प्रत्याशित वाली हैश तालिका के बजाय O(log n) प्रत्याभूत वाला संतुलित वृक्ष प्रयोग करता है।