K-क्रमबद्ध अनुक्रम: Difference between revisions

Latest revision as of 09:55, 11 August 2023

कंप्यूटर विज्ञान में क्रमबद्ध अनुक्रम, जिसे अधिकतर क्रमबद्ध अनुक्रम और K के रूप में जाना जाता है $k$ -सॉर्टेड अनुक्रम का एक अनुक्रम है जो लगभग क्रमबद्ध होता है। क्रमबद्ध अनुक्रम से तात्पर्य यह है कि अनुक्रम का कोई भी तत्व उस स्थान से बहुत दूर नहीं है जहाँ वह होता यदि अनुक्रम पूर्णतः क्रमबद्ध है तो यह अभी भी संभव है कि अनुक्रम का कोई भी तत्व उस स्थान पर नहीं है जहां उसे होना चाहिए यदि अनुक्रम पूरी तरह से व्यवस्थित होता है।

लगभग क्रमबद्ध क्रम तब उपयोगी होते हैं जब तत्व के सही क्रम का कोई महत्व नहीं होता है। उदाहरण के लिए ट्विटर^[1] ट्वीट्स को लगभग क्रमबद्ध करें, क्योंकि इसमें अधिक सही होने की आवश्यकता नहीं होती,जबकि सभी कंप्यूटरों को सटीक रूप से विवरण करने की असंभवता को देखते हुए, सभी ट्वीट्स को उनके पोस्ट किए जाने के समय के अनुसार क्रमबद्ध करना असंभव है इस विचार के कारण स्नोफ्लेक आईडी का निर्माण हुआ $k$ -सॉर्टिंग एक अनुक्रम के तत्वों को पुन: व्यवस्थित करने का संचालन है जिससे $k$ -क्रमबद्ध $k$ - पृथककरण से अधिक कुशल होता है। इसी प्रकार किसी अनुक्रम को क्रमबद्ध करना आसान होता है यदि यह ज्ञात हो कि अनुक्रम $k$ -क्रमबद्ध है, इसलिए यदि किसी कार्यक्रम पर विचार करने की आवश्यकता होती है तो $k$ इनपुट या आउटपुट के रूप में क्रमबद्ध अनुक्रम में $k$ -क्रमबद्ध क्रम से समय की बचत हो सकती है।

किसी अनुक्रम की त्रिज्या पूर्व-क्रमबद्धता की एक माप है अर्थात, इसका मान यह दर्शाता है कि पूरी तरह से क्रमबद्ध मान प्राप्त करने के लिए सूची में तत्वों को कितना स्थानांतरित करना होगा ट्वीट्स के उदाहरण में जिन्हें दूसरे तक क्रमबद्ध किया गया है तथा एक सेकंड में ट्वीट्स की संख्या से अनुक्रम सीमित है।

परिभाषा

एक सकारात्मक संख्या दी गई $k$ , एक क्रम में $[a_{1},\dots ,a_{n}]$ बताया गया कि $k$ -यदि प्रत्येक के लिए क्रमबद्ध और $1\leq i$ प्रत्येक के लिए $i+k\leq j\leq n$ , $a_{i}\leq a_{j}$ . अर्थात् अनुक्रम को केवल उन तत्वों के युग्मों के लिए क्रमबद्ध करना होगा जिनकी दूरी कम से कम हो $k$ .

अनुक्रम की त्रिज्या $\alpha$ , निरूपित ${\text{ROUGH}}(\alpha )$ ^[2] या ${\text{Par}}(\alpha )$ ^[3] सबसे छोटा है $k$ ऐसा कि क्रम है $k$ -क्रमबद्ध त्रिज्या पूर्व निर्धारितता की माप है।

किसी अनुक्रम को लगभग क्रमबद्ध या अनुक्रम क्रमबद्ध कहा जाता है इसकी त्रिज्या इसकी लंबाई की तुलना में छोटी होती है।

समतुल्य परिभाषा

एक क्रम $[a_{1},\dots ,a_{n}]$ है $k$ - केवल लंबाई की प्रत्येक सीमा को क्रमबद्ध करता है तथा $2k+2$ , $[a_{i},a_{i+1},\dots ,a_{i+2k+2}]$ $k$ -क्रमबद्ध अनुक्रम है।

गुण

लंबाई के सभी क्रम $n$ हैं $(n-1)$ -क्रमबद्ध अर्थात्, $0\leq {\text{Par}}([a_{1},\dots ,a_{n}])<n$ . एक क्रम है $0$ -लघु किया गया यदि इसे लघु किया गया है तो $k$ -क्रमबद्ध अनुक्रम स्वचालित रूप से है $(k+1)$ -क्रमबद्ध जरूरी नहीं है लेकिन $(k-1)$ -क्रमबद्ध है।

क्रमबद्ध अनुक्रमों के साथ संबंध

एक क्रम दिया गया है a $k$ -क्रमबद्ध क्रम, $[a_{1},\dots ,a_{n}]$ और इसका क्रम परिवर्तन $[a_{\sigma _{1}},\dots ,a_{\sigma _{n}}]$ , $|i-\sigma _{i}|$ अधिकतम है $k$ .

प्रारूप

यह तय करना कि कोई अनुक्रम है या नहीं $k$ - क्रमबद्ध

इसमें यह तय करना कि क्या अनुक्रम है $[a_{1},\dots ,a_{n}]$ $k$ - योग्य प्रारूप द्वारा रैखिक समय और स्थिर स्थान में लघु व जटिलता से क्रमबद्ध किया जा सकता है, जो प्रत्येक के लिए पर्याप्त है $1\leq i<n-k$ , इस पर नज़र रखने के लिए $\max(a_{j}\mid j\leq i)$ और उसे जॉंचने के लिए यह महत्वपूर्ण है।

किसी अनुक्रम की त्रिज्या की गणना रैखिक समय और कुछ स्थानों में की जा सकती है, यह इस तथ्य से पता चलता है कि इसे किस प्रकार परिभाषित किया जा सकता है $\max(i-j\mid \min(a_{k}\mid k\geq i)<\max(a_{k}\mid k\leq j))$ .

अनुक्रम की त्रिज्या को आधा करना

दिया गया ए $2k$ -क्रमबद्ध क्रम $\alpha =[a_{1},\dots ,a_{n}]$ , इसकी गणना करना संभव है $(k-1)$ -क्रमबद्ध क्रमपरिवर्तन $\alpha '$ का $\alpha$ रैखिक समय और स्थिर स्थान में

सबसे पहले एक क्रम में दिया गया है $\beta =[b_{1},\dots ,b_{2k}]$ मान लें कि यह अनुक्रम विभाजित है यदि $k$ -छोटे तत्व अंदर हैं $[b_{1},\dots ,b_{k}]$ और $k$ -बड़े तत्व अंदर हैं $[b_{k+1},\dots ,b_{2k}]$ . तो अनुक्रम को पुनः व्यवस्थित करने की क्रिया को विभाजन कहते हैं $\beta$ एक विभाजित क्रमपरिवर्तन में इसे पहले माध्यिका ज्ञात करके रैखिक समय में क्रमबद्ध करता है और $b$ फिर तत्वों को पहले या दूसरे भाग में ले जाता है यह इस पर निर्भर करता है कि वे माध्यिका से छोटे या बड़े हैं।

क्रम $\alpha '$ तत्वों के ब्लॉकों को उनके स्थान पर विभाजित करके प्राप्त किया जा सकता है $[2k(i-1)+1,\dots ,2ki]$ , फिर तत्वों के ब्लॉकों को उनके स्थान पर विभाजित करके $[2k(i-1)+k+1,\dots ,2ki+k]$ , और उसके बाद फिर से स्थिति पर तत्व $[2k(i-1)+1,\dots ,2ki]$ प्रत्येक संख्या के लिए $i$ जैसे कि उन अनुक्रमों को परिभाषित किया गया है।

इसका उपयोग करते हुए ${\frac {n}{2k}}$ प्रोसेसर जिसमें स्मृति तक कोई साझा पढ़ने और लिखने की पहुंच में नहीं है, जबकि इसमें उसी प्रारूप को लागू किया जा सकता है जिसका $O(k)$ समय,अनुक्रम का प्रत्येक विभाजन समानांतर में हो सकता है।

दो को मिलाना $k$ -क्रमबद्ध अनुक्रम

दो का विलय $k$ -क्रमबद्ध अनुक्रम $\alpha ^{1}=[a_{1}^{1},\dots ,a_{n}^{1}]$ और $\alpha =[a_{1}^{2},\dots ,a_{m}^{2}]$ रैखिक समय स्थिर स्थान में प्रयोग किया जा सकता है।

सबसे पहले पूर्ववर्ती प्रारूप का उपयोग करके, दोनों अनुक्रमों को $k/2$ -क्रमबद्ध अनुक्रम में रूपांतरित किया जाना चाहिए।

पुनरावर्ती रूप से एक आउटपुट अनुक्रम बनाएं $\omega$ दोनों से सामग्री हटाकर $\alpha ^{i}$ व $\omega$ जोड़ दिया जाता है।

अगर दोनों $\alpha ^{i}$ खाली हैं तो लौटना ही काफी है तो $\omega$ मान लेते हैं $\alpha ^{1}$ खाली है $\alpha ^{2}$ , इसकी सामग्री को हटाना पर्याप्त है $\alpha ^{2}$ और इसे संलग्न करें $\omega$ . $\alpha ^{2}$ खाली है और $\alpha ^{1}$ समरूपता से समान है।

आइए उस जगह पर विचार करें जहां न तो $\alpha ^{i}$ खाली है जो इस प्रकार है- $A^{1}=\max(a_{i}^{1}\mid 1\leq i\leq k/2)$ और $A^{2}=\max(a_{i}^{2}\mid 1\leq i\leq k/2)$ , वे सबसे महान हैं $k/2$ -प्रथम प्रत्येक सूची के तत्व हैं $A^{1}<A^{2}$ , दूसरा स्थान समरूपता के समान है। जहाँ $a_{1}^{1},\dots ,a_{k/2}^{1}$ से $\alpha ^{1}$ हटाओ । $\{a_{j}^{2}\mid 1\leq j\leq k/2,a_{j}^{2}\leq A^{1}\}$ से $\alpha ^{2}$ $\omega$ में जोड़ें।

सॉर्टिंग ए $k$ -क्रमबद्ध अनुक्रम

ए $k$ -क्रमबद्ध क्रम को ऊपर दिए गए हाफिंग प्रारूप को लागू करके क्रमबद्ध किया जा सकता है $\log _{2}(k)$ बार यह लेता है कि $O(n\log k)$ अनुक्रमिक मशीन पर समय या $O(k\log k)$ समय का उपयोग $O(n)$ प्रोसेसर द्वारा किया जाता है।

$k$ -एक अनुक्रम को क्रमबद्ध करना

प्रत्येक अनुक्रम के बाद से $\alpha =[a_{1},\dots ,a_{n}]$ आवश्यक है $n$ -लघु किया गया यह हॉल्टिंग प्रारूप को लागू करने के लिए पर्याप्त है $\log _{2}\left({\frac {n}{k}}\right)$ -समय इस प्रकार, $k$ -सॉर्टिंग की जा सकती है $O(n\log(n/k))$ -समय यह प्रारूप एम-इष्टतम छँटाई है, यानी बेहतर सबसे खराब स्थिति वाली जटिलता वाला कोई अनुक्रमिक प्रारूप एकत्र नहीं है।

संदर्भ

↑ @rk. "स्नोफ्लेक की घोषणा". Twitter blog. Retrieved 26 April 2021.
↑ Altman, Tom; Igarashi, Yoshihide (1989-08-25). "Roughly Sorting: Sequential and Parallel Approach". Journal of Information Processing. 12 (2): 154–158.
↑ Estivill-Castro, Vladimir; Wood, Derick (October 1989). "विविधता का एक नया उपाय". Information and Computation. 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3.

[twitter-1] @rk. "स्नोफ्लेक की घोषणा". Twitter blog. Retrieved 26 April 2021.

[altma-Igarashi-2] Altman, Tom; Igarashi, Yoshihide (1989-08-25). "Roughly Sorting: Sequential and Parallel Approach". Journal of Information Processing. 12 (2): 154–158.

[Estivill-Castro-Wood-3] Estivill-Castro, Vladimir; Wood, Derick (October 1989). "विविधता का एक नया उपाय". Information and Computation. 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{Orphan|date=October 2021}}
-[[कंप्यूटर विज्ञान]] में क्रमबद्ध अनुक्रम, जिसे अधिकतर कमबद्ध अनुक्रम के रूप में जाना जाता है<math>k</math>-सॉर्टेड अनुक्रम का एक अनुक्रम है जो लगभग क्रमबद्ध होता है। क्रमबद्ध अनुक्रम से तात्पर्य यह है कि अनुक्रम का कोई भी तत्व उस स्थान से बहुत दूर नहीं है जहाँ वह होता यदि अनुक्रम पूर्णतः क्रमबद्ध है तो यह अभी भी संभव है कि अनुक्रम का कोई भी तत्व उस स्थान पर नहीं है जहां उसे होना चाहिए यदि अनुक्रम पूरी तरह से व्यवस्थित होता।
+[[कंप्यूटर विज्ञान]] में क्रमबद्ध अनुक्रम, जिसे अधिकतर क्रमबद्ध अनुक्रम और K के रूप में जाना जाता है<math>k</math>-सॉर्टेड अनुक्रम का एक अनुक्रम है जो लगभग क्रमबद्ध होता है। क्रमबद्ध अनुक्रम से तात्पर्य यह है कि अनुक्रम का कोई भी तत्व उस स्थान से बहुत दूर नहीं है जहाँ वह होता यदि अनुक्रम पूर्णतः क्रमबद्ध है तो यह अभी भी संभव है कि अनुक्रम का कोई भी तत्व उस स्थान पर नहीं है जहां उसे होना चाहिए यदि अनुक्रम पूरी तरह से व्यवस्थित होता है।
-लगभग क्रमबद्ध क्रम विशेष रूप से तब उपयोगी होते हैं जब तत्व के सही क्रम का कोई महत्व नहीं होता है। उदाहरण के लिए [[ट्विटर]]<ref name="twitter">{{cite web |last1=@rk |title=स्नोफ्लेक की घोषणा|url=https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html |website=Twitter blog |access-date=26 April 2021}}</ref> ट्वीट्स को लगभग क्रमबद्ध करें, क्योंकि अधिक सटीकता की आवश्यकता नहीं होती,जबकि सभी कंप्यूटरों को सटीक रूप से सिंक्रनाइज़ करने की असंभवता को देखते हुए, सभी ट्वीट्स को उनके पोस्ट किए जाने के समय के अनुसार सटीक क्रमबद्ध करना असंभव है इस विचार के कारण [[स्नोफ्लेक आईडी]] का निर्माण हुआ <math>k</math>-सॉर्टिंग एक अनुक्रम के तत्वों को पुन: व्यवस्थित करने का संचालन है जिससे <math>k</math>-क्रमबद्ध <math>k</math>-सॉर्टिंग अधिकतर सॉर्टिंग से अधिक कुशल होती है। इसी प्रकार, किसी अनुक्रम को क्रमबद्ध करना आसान होता है यदि यह ज्ञात हो कि अनुक्रम <math>k</math>-क्रमबद्ध, इसलिए यदि किसी कार्यक्रम पर केवल विचार करने की आवश्यकता होती है तो <math>k</math>इनपुट या आउटपुट के रूप में क्रमबद्ध अनुक्रम में <math>k</math>-क्रमबद्ध क्रम से समय की बचत हो सकती है।
+लगभग क्रमबद्ध क्रम तब उपयोगी होते हैं जब तत्व के सही क्रम का कोई महत्व नहीं होता है। उदाहरण के लिए [[ट्विटर]]<ref name="twitter">{{cite web |last1=@rk |title=स्नोफ्लेक की घोषणा|url=https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html |website=Twitter blog |access-date=26 April 2021}}</ref> ट्वीट्स को लगभग क्रमबद्ध करें, क्योंकि इसमें अधिक सही होने की आवश्यकता नहीं होती,जबकि सभी कंप्यूटरों को सटीक रूप से विवरण करने की असंभवता को देखते हुए, सभी ट्वीट्स को उनके पोस्ट किए जाने के समय के अनुसार क्रमबद्ध करना असंभव है इस विचार के कारण [[स्नोफ्लेक आईडी]] का निर्माण हुआ <math>k</math>-सॉर्टिंग एक अनुक्रम के तत्वों को पुन: व्यवस्थित करने का संचालन है जिससे <math>k</math>-क्रमबद्ध <math>k</math>- पृथककरण से अधिक कुशल होता है। इसी प्रकार किसी अनुक्रम को क्रमबद्ध करना आसान होता है यदि यह ज्ञात हो कि अनुक्रम <math>k</math>-क्रमबद्ध है, इसलिए यदि किसी कार्यक्रम पर विचार करने की आवश्यकता होती है तो <math>k</math>इनपुट या आउटपुट के रूप में क्रमबद्ध अनुक्रम में <math>k</math>-क्रमबद्ध क्रम से समय की बचत हो सकती है।
-किसी अनुक्रम की त्रिज्या पूर्व-क्रमबद्धता का एक माप है अर्थात, इसका मान यह इंगित करता है कि पूरी तरह से क्रमबद्ध मान प्राप्त करने के लिए सूची में तत्वों को कितना स्थानांतरित करना होगा ट्वीट्स के उपरोक्त उदाहरण में, जिन्हें दूसरे तक क्रमबद्ध किया गया है,तथा एक सेकंड में ट्वीट्स की संख्या से अनुक्रम सीमित है।
+किसी अनुक्रम की त्रिज्या पूर्व-क्रमबद्धता की एक माप है अर्थात, इसका मान यह दर्शाता है कि पूरी तरह से क्रमबद्ध मान प्राप्त करने के लिए सूची में तत्वों को कितना स्थानांतरित करना होगा ट्वीट्स के उदाहरण में जिन्हें दूसरे तक क्रमबद्ध किया गया है तथा एक सेकंड में ट्वीट्स की संख्या से अनुक्रम सीमित है।
 == परिभाषा ==
-एक सकारात्मक संख्या दी गई <math>k</math>, एक क्रम में <math>[a_1,\dots, a_n]</math> बताया गया कि <math>k</math>-यदि प्रत्येक के लिए क्रमबद्ध <math>1\le i</math> और प्रत्येक के लिए <math>i+k\le j\le n</math>, <math>a_i\le a_j</math>. अर्थात् अनुक्रम को केवल उन तत्वों के युग्मों के लिए क्रमबद्ध करना होगा जिनकी दूरी कम से कम हो <math>k</math>.
+एक सकारात्मक संख्या दी गई <math>k</math>, एक क्रम में <math>[a_1,\dots, a_n]</math> बताया गया कि <math>k</math>-यदि प्रत्येक के लिए क्रमबद्ध और <math>1\le i</math> प्रत्येक के लिए <math>i+k\le j\le n</math>, <math>a_i\le a_j</math>. अर्थात् अनुक्रम को केवल उन तत्वों के युग्मों के लिए क्रमबद्ध करना होगा जिनकी दूरी कम से कम हो <math>k</math>.
-अनुक्रम की त्रिज्या <math>\alpha</math>, निरूपित <math>\text{ROUGH}(\alpha)</math><ref name="altma-Igarashi">{{cite journal |last1=Altman |first1=Tom |last2=Igarashi |first2=Yoshihide |title=Roughly Sorting: Sequential and Parallel Approach |journal=Journal of Information Processing |date=1989-08-25 |volume=12 |issue=2 |pages=154–158 }}</ref> या <math>\text{Par}(\alpha)</math><ref name="Estivill-Castro-Wood">{{cite journal |last1=Estivill-Castro |first1=Vladimir |last2=Wood |first2=Derick |title=विविधता का एक नया उपाय|journal=Information and Computation |date=October 1989 |volume=83 |issue=1 |pages=111–119 |doi=10.1016/0890-5401(89)90050-3|doi-access=free }}</ref> सबसे छोटा है <math>k</math> ऐसा कि क्रम है <math>k</math>-क्रमबद्ध त्रिज्या पूर्वनिर्धारितता की माप है।
+अनुक्रम की त्रिज्या <math>\alpha</math>, निरूपित <math>\text{ROUGH}(\alpha)</math><ref name="altma-Igarashi">{{cite journal |last1=Altman |first1=Tom |last2=Igarashi |first2=Yoshihide |title=Roughly Sorting: Sequential and Parallel Approach |journal=Journal of Information Processing |date=1989-08-25 |volume=12 |issue=2 |pages=154–158 }}</ref> या <math>\text{Par}(\alpha)</math><ref name="Estivill-Castro-Wood">{{cite journal |last1=Estivill-Castro |first1=Vladimir |last2=Wood |first2=Derick |title=विविधता का एक नया उपाय|journal=Information and Computation |date=October 1989 |volume=83 |issue=1 |pages=111–119 |doi=10.1016/0890-5401(89)90050-3|doi-access=free }}</ref> सबसे छोटा है <math>k</math> ऐसा कि क्रम है <math>k</math>-क्रमबद्ध त्रिज्या पूर्व निर्धारितता की माप है।
-किसी अनुक्रम को लगभग क्रमबद्ध या अनुक्रम क्रमबद्ध कहा जाता है यदि इसकी त्रिज्या इसकी लंबाई की तुलना में छोटी हो।
+किसी अनुक्रम को लगभग क्रमबद्ध या अनुक्रम क्रमबद्ध कहा जाता है  इसकी त्रिज्या इसकी लंबाई की तुलना में छोटी होती है।
 === समतुल्य परिभाषा ===
-एक क्रम <math>[a_1,\dots, a_n]</math> है <math>k</math>- केवल लंबाई की प्रत्येक सीमा को क्रमबद्ध किया जाता है <math>2k+2</math>, <math>[a_i, a_{i+1},\dots, a_{i+2k+2}]</math> <math>k</math>-क्रमबद्ध अनुक्रम है।
+एक क्रम <math>[a_1,\dots, a_n]</math> है <math>k</math>- केवल लंबाई की प्रत्येक सीमा को क्रमबद्ध करता है तथा <math>2k+2</math>, <math>[a_i, a_{i+1},\dots, a_{i+2k+2}]</math> <math>k</math>-क्रमबद्ध अनुक्रम है।
 == गुण ==
-लंबाई के सभी क्रम <math>n</math> हैं <math>(n-1)</math>-क्रमबद्ध, अर्थात्, <math>0\le \text{Par}([a_1,\dots,a_n])<n</math>. एक क्रम है <math>0</math>-सॉर्ट किया गया यदि और केवल यदि इसे सॉर्ट किया गया है। ए <math>k</math>-क्रमबद्ध अनुक्रम स्वचालित रूप से है <math>(k+1)</math>-क्रमबद्ध लेकिन जरूरी नहीं <math>(k-1)</math>-क्रमबद्ध।
+लंबाई के सभी क्रम <math>n</math> हैं <math>(n-1)</math>-क्रमबद्ध अर्थात्, <math>0\le \text{Par}([a_1,\dots,a_n])<n</math>. एक क्रम है <math>0</math>-लघु किया गया यदि  इसे लघु किया गया है तो <math>k</math>-क्रमबद्ध अनुक्रम स्वचालित रूप से है <math>(k+1)</math>-क्रमबद्ध जरूरी नहीं है लेकिन <math>(k-1)</math>-क्रमबद्ध है।
 === क्रमबद्ध अनुक्रमों के साथ संबंध ===
-एक क्रम दिया गया है a <math>k</math>-क्रमबद्ध क्रम <math>[a_1,\dots, a_n]</math> और इसका क्रमपरिवर्तन <math>[a_{\sigma_1},\dots, a_{\sigma_n}]</math>, <math>|i-\sigma_i|</math> अधिकतम है <math>k</math>.
+एक क्रम दिया गया है a <math>k</math>-क्रमबद्ध क्रम, <math>[a_1,\dots, a_n]</math> और इसका क्रम परिवर्तन <math>[a_{\sigma_1},\dots, a_{\sigma_n}]</math>, <math>|i-\sigma_i|</math> अधिकतम है <math>k</math>.
-== एल्गोरिदम ==
+== प्रारूप ==
-=== यह तय करना कि कोई अनुक्रम है या नहीं <math>k</math>-क्रमबद्ध ===
+=== यह तय करना कि कोई अनुक्रम है या नहीं <math>k</math>- क्रमबद्ध ===
-यह तय करना कि क्या कोई अनुक्रम है <math>[a_1,\dots, a_n]</math> है <math>k</math>-[[स्ट्रीमिंग एल्गोरिदम]] द्वारा [[रैखिक समय]] और स्थान जटिलता में क्रमबद्ध किया जा सकता है। यह प्रत्येक के लिए पर्याप्त है <math>1\le i < n-k</math>, इस पर नज़र रखने के लिए <math>\max(a_j\mid j\le i)</math> और उसे जांचने के लिए <math>a_{i+k}\ge\max(a_j\mid j\le i)</math>.
-=== अनुक्रम की त्रिज्या की गणना ===
-किसी अनुक्रम की त्रिज्या की गणना रैखिक समय और स्थान में की जा सकती है। यह इस तथ्य से पता चलता है कि इसे इस प्रकार परिभाषित किया जा सकता है <math>\max(i-j\mid \min(a_k\mid k\ge i) < \max(a_k\mid k\le j))</math>.
+इसमें यह तय करना कि क्या अनुक्रम है <math>[a_1,\dots, a_n]</math> <math>k</math>- [[स्ट्रीमिंग एल्गोरिदम|योग्य]] प्रारूप द्वारा [[रैखिक समय]] और स्थिर स्थान में लघु व जटिलता से क्रमबद्ध किया जा [[रैखिक समय|सकता]] है, जो प्रत्येक के लिए पर्याप्त है <math>1\le i < n-k</math>, इस पर नज़र रखने के लिए <math>\max(a_j\mid j\le i)</math> और उसे जॉंचने के लिए यह महत्वपूर्ण है।
+किसी अनुक्रम की त्रिज्या की गणना रैखिक समय और कुछ स्थानों में की जा सकती है, यह इस तथ्य से पता चलता है कि इसे किस प्रकार परिभाषित किया जा सकता है <math>\max(i-j\mid \min(a_k\mid k\ge i) < \max(a_k\mid k\le j))</math>.
 === अनुक्रम की त्रिज्या को आधा करना ===
-दिया गया ए <math>2k</math>-क्रमबद्ध क्रम <math>\alpha=[a_1,\dots, a_n]</math>, इसकी गणना करना संभव है <math>(k-1)</math>-क्रमबद्ध क्रमपरिवर्तन <math>\alpha'</math> का <math>\alpha</math> रैखिक समय और स्थिर स्थान में.
+दिया गया ए <math>2k</math>-क्रमबद्ध क्रम <math>\alpha=[a_1,\dots, a_n]</math>, इसकी गणना करना संभव है <math>(k-1)</math>-क्रमबद्ध क्रमपरिवर्तन <math>\alpha'</math> का <math>\alpha</math> रैखिक समय और स्थिर स्थान में
-सबसे पहले, एक क्रम दिया गया <math>\beta=[b_1,\dots,b_{2k}]</math>, मान लें कि यह अनुक्रम विभाजित है यदि <math>k</math>-छोटे तत्व अंदर हैं <math>[b_1,\dots,b_k]</math> और यह <math>k</math>-बड़े तत्व अंदर हैं <math>[b_{k+1},\dots, b_{2k}]</math>. आइए अनुक्रम को पुनः व्यवस्थित करने की क्रिया को विभाजन कहते हैं <math>\beta</math> एक विभाजित क्रमपरिवर्तन में. इसे पहले माध्यिका ज्ञात करके रैखिक समय में किया जा सकता है <math>b</math> और फिर तत्वों को पहले या दूसरे भाग में ले जाना इस पर निर्भर करता है कि वे माध्यिका से छोटे हैं या बड़े।
+सबसे पहले एक क्रम में दिया गया है <math>\beta=[b_1,\dots,b_{2k}]</math> मान लें कि यह अनुक्रम विभाजित है यदि <math>k</math>-छोटे तत्व अंदर हैं <math>[b_1,\dots,b_k]</math> और  <math>k</math>-बड़े तत्व अंदर हैं <math>[b_{k+1},\dots, b_{2k}]</math>. तो अनुक्रम को पुनः व्यवस्थित करने की क्रिया को विभाजन कहते हैं <math>\beta</math> एक विभाजित क्रमपरिवर्तन में इसे पहले माध्यिका ज्ञात करके रैखिक समय में क्रमबद्ध करता है और <math>b</math> फिर तत्वों को पहले या दूसरे भाग में ले जाता है यह इस पर निर्भर करता है कि वे माध्यिका से छोटे या बड़े हैं।
 क्रम <math>\alpha'</math> तत्वों के ब्लॉकों को उनके स्थान पर विभाजित करके प्राप्त किया जा सकता है <math>[2k(i-1)+1, \dots, 2ki]</math>, फिर तत्वों के ब्लॉकों को उनके स्थान पर विभाजित करके <math>[2k(i-1)+k+1, \dots, 2ki+k]</math>, और उसके बाद फिर से स्थिति पर तत्व  <math>[2k(i-1)+1, \dots, 2ki]</math> प्रत्येक संख्या के लिए <math>i</math> जैसे कि उन अनुक्रमों को परिभाषित किया गया है।
-का उपयोग करते हुए <math>\frac{n}{2k}</math> प्रोसेसर, जिसमें मेमोरी तक कोई साझा पढ़ने और लिखने की पहुंच नहीं है, उसी एल्गोरिदम को लागू किया जा सकता है <math>O(k)</math> समय, क्योंकि अनुक्रम का प्रत्येक विभाजन समानांतर में हो सकता है।
+इसका उपयोग करते हुए <math>\frac{n}{2k}</math> प्रोसेसर जिसमें स्मृति तक कोई साझा पढ़ने और लिखने की पहुंच में नहीं है, जबकि इसमें उसी प्रारूप को लागू किया जा सकता है जिसका <math>O(k)</math> समय,अनुक्रम का प्रत्येक विभाजन समानांतर में हो सकता है।
 ===दो को मिलाना <math>k</math>-क्रमबद्ध अनुक्रम ===
 {{distinguish|k-way merge algorithm}}
-दो का विलय <math>k</math>-क्रमबद्ध अनुक्रम <math>\alpha^1=[a^1_1,\dots, a^1_n]</math> और <math>\alpha=[a^2_1,\dots, a^2_m]</math> रैखिक समय और स्थिर स्थान में किया जा सकता है।
+दो का विलय <math>k</math>-क्रमबद्ध अनुक्रम <math>\alpha^1=[a^1_1,\dots, a^1_n]</math> और <math>\alpha=[a^2_1,\dots, a^2_m]</math> रैखिक समय स्थिर स्थान में प्रयोग किया जा सकता है।
-सबसे पहले, पूर्ववर्ती एल्गोरिदम का उपयोग करके, दोनों अनुक्रमों को रूपांतरित किया जाना चाहिए <math>k/2</math>-क्रमबद्ध अनुक्रम।
+सबसे पहले पूर्ववर्ती प्रारूप का उपयोग करके, दोनों अनुक्रमों को <math>k/2</math>-क्रमबद्ध अनुक्रम में रूपांतरित किया जाना चाहिए।
-आइए पुनरावर्ती रूप से एक आउटपुट अनुक्रम बनाएं <math>\omega</math> दोनों से सामग्री हटाकर <math>\alpha^i</math> और इसे इसमें जोड़ रहा हूँ <math>\omega</math>.
+पुनरावर्ती रूप से एक आउटपुट अनुक्रम बनाएं <math>\omega</math> दोनों से सामग्री हटाकर <math>\alpha^i</math> व <math>\omega</math> जोड़ दिया जाता है।
-अगर दोनों <math>\alpha^i</math>के खाली हैं, तो लौटना ही काफी है <math>\omega</math>. नहीं तो चलिए मान लेते हैं <math>\alpha^1</math> खाली है और नहीं <math>\alpha^2</math>, इसकी सामग्री को हटाना पर्याप्त है <math>\alpha^2</math> और इसे संलग्न करें <math>\omega</math>. मामला जहां <math>\alpha^2</math> खाली है और नहीं <math>\alpha^1</math> समरूपता से समान है।
+अगर दोनों <math>\alpha^i</math> खाली हैं तो लौटना ही काफी है तो <math>\omega</math> मान लेते हैं <math>\alpha^1</math> खाली है  <math>\alpha^2</math>, इसकी सामग्री को हटाना पर्याप्त है <math>\alpha^2</math> और इसे संलग्न करें <math>\omega</math>. <math>\alpha^2</math> खाली है और <math>\alpha^1</math> समरूपता से समान है।
-आइए उस मामले पर विचार करें जहां न तो <math>\alpha^i</math> खाली है। आइए कॉल करें <math>A^1=\max(a^1_i\mid 1\le i\le
+आइए उस जगह पर विचार करें जहां न तो <math>\alpha^i</math> खाली है  जो इस प्रकार है-<math>A^1=\max(a^1_i\mid 1\le i\le
-k/2)</math> और <math>A^2=\max(a^2_i\mid 1\le i\le k/2)</math>, वे सबसे महान हैं <math>k/2</math>-प्रथम
+k/2)</math> और <math>A^2=\max(a^2_i\mid 1\le i\le k/2)</math>, वे सबसे महान हैं <math>k/2</math>-प्रथम प्रत्येक सूची के तत्व हैं <math>A^1<A^2</math>, दूसरा स्थान समरूपता के समान है। जहाँ <math>a^1_1,\dots, a^1_{k/2}</math> से <math>\alpha^1</math>  हटाओ ।<math>\{a^2_j\mid 1\le j\le k/2, a^2_j\le
-प्रत्येक सूची के तत्व. चलिए मान लेते हैं <math>A^1<A^2</math>, दूसरा मामला समरूपता के समान है। निकालना
+A^1\}</math> से <math>\alpha^2</math> <math>\omega</math> में जोड़ें।
-<math>a^1_1,\dots, a^1_{k/2}</math> से <math>\alpha^1</math> और हटाओ <math>\{a^2_j\mid 1\le j\le k/2, a^2_j\le
-A^1\}</math> से <math>\alpha^2</math> और उन्हें जोड़ें <math>\omega</math>.
 === सॉर्टिंग ए <math>k</math>-क्रमबद्ध अनुक्रम ===
-ए <math>k</math>-क्रमबद्ध क्रम को ऊपर दिए गए हाफिंग एल्गोरिदम को लागू करके क्रमबद्ध किया जा सकता है <math>\log_2(k)</math> बार. यह लेता है <math>O(n\log k)</math> अनुक्रमिक मशीन पर समय, या <math>O(k\log k)</math> समय का उपयोग <math>O(n)</math> प्रोसेसर.
+ए <math>k</math>-क्रमबद्ध क्रम को ऊपर दिए गए हाफिंग प्रारूप को लागू करके क्रमबद्ध किया जा सकता है <math>\log_2(k)</math> बार यह लेता है कि <math>O(n\log k)</math> अनुक्रमिक मशीन पर समय या <math>O(k\log k)</math> समय का उपयोग <math>O(n)</math> प्रोसेसर द्वारा किया जाता है।
 === <math>k</math>-एक अनुक्रम को क्रमबद्ध करना ===
-प्रत्येक अनुक्रम के बाद से <math>\alpha=[a_1,\dots, a_n]</math> आवश्यक है <math>n</math>-सॉर्ट किया गया, यह हॉल्टिंग एल्गोरिदम को लागू करने के लिए पर्याप्त है <math>\log_{2}\left(\frac{n}{k}\right)</math>-समय. इस प्रकार, <math>k</math>-सॉर्टिंग की जा सकती है <math>O(n\log (n/k))</math>-समय। यह एल्गोरिदम [[ एम-इष्टतम छँटाई ]]-इष्टतम है, यानी, बेहतर सबसे खराब स्थिति वाली जटिलता वाला कोई अनुक्रमिक एल्गोरिदम मौजूद नहीं है।
+प्रत्येक अनुक्रम के बाद से <math>\alpha=[a_1,\dots, a_n]</math> आवश्यक है <math>n</math>-लघु किया गया यह हॉल्टिंग प्रारूप को लागू करने के लिए पर्याप्त है <math>\log_{2}\left(\frac{n}{k}\right)</math>-समय इस प्रकार, <math>k</math>-सॉर्टिंग की जा सकती है <math>O(n\log (n/k))</math>-समय यह प्रारूप[[ एम-इष्टतम छँटाई | एम-इष्टतम छँटाई]] है, यानी बेहतर सबसे खराब स्थिति वाली जटिलता वाला कोई अनुक्रमिक प्रारूप एकत्र नहीं है।
 == संदर्भ ==
@@ Line 77: / Line 75: @@
 {{sorting}}
-{{DEFAULTSORT:Comparison Sort}}[[Category: छँटाई एल्गोरिदम]]
+{{DEFAULTSORT:Comparison Sort}}
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Comparison Sort]]
-[[Category:Created On 26/07/2023]]
+[[Category:Collapse templates|Comparison Sort]]
+[[Category:Created On 26/07/2023|Comparison Sort]]
+[[Category:Machine Translated Page|Comparison Sort]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Comparison Sort]]
+[[Category:Pages with script errors|Comparison Sort]]
+[[Category:Sidebars with styles needing conversion|Comparison Sort]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats|Comparison Sort]]
+[[Category:Templates that are not mobile friendly|Comparison Sort]]
+[[Category:Templates using TemplateData|Comparison Sort]]
+[[Category:Wikipedia metatemplates|Comparison Sort]]
+[[Category:छँटाई एल्गोरिदम|Comparison Sort]]

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

K-क्रमबद्ध अनुक्रम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:55, 11 August 2023

Contents