K-क्रमबद्ध अनुक्रम

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

लगभग क्रमबद्ध क्रम विशेष रूप से तब उपयोगी होते हैं जब तत्व के सही क्रम का कोई महत्व नहीं होता है। उदाहरण के लिए ट्विटर ट्वीट्स को लगभग क्रमबद्ध करें, क्योंकि अधिक सटीकता की आवश्यकता नहीं होती,जबकि सभी कंप्यूटरों को सटीक रूप से सिंक्रनाइज़ करने की असंभवता को देखते हुए, सभी ट्वीट्स को उनके पोस्ट किए जाने के समय के अनुसार सटीक क्रमबद्ध करना असंभव है इस विचार के कारण स्नोफ्लेक आईडी का निर्माण हुआ $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 )$ या ${\text{Par}}(\alpha )$ सबसे छोटा है $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)$ और उसे जांचने के लिए $a_{i+k}\geq \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$-क्रमबद्ध अनुक्रम

Not to be confused with k-way merge algorithm.

दो का विलय $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))$-समय। यह एल्गोरिदम एम-इष्टतम छँटाई -इष्टतम है, यानी, बेहतर सबसे खराब स्थिति वाली जटिलता वाला कोई अनुक्रमिक एल्गोरिदम मौजूद नहीं है।