تشغيل تسلسل

في علم الحاسوب ، تُعرف سلسلة متتالية بأنها نطاق غير متناقص من المتتالية لا يمكن تمديده. ويُعرف عدد السلاسل المتتالية بعدد السلاسل الفرعية المتزايدة من المتتالية. وهذا مقياس للترتيب المسبق ، ويقيس تحديدًا عدد السلاسل الفرعية التي يجب دمجها لترتيب المتتالية.

يترك${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ليكن تسلسلًا من العناصر من مجموعة مرتبة ترتيبًا كليًا . سلسلة من${\displaystyle X}$هي متتالية متزايدة قصوى${\displaystyle \langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle }$. إنه،${\displaystyle x_{i-1}>x_{i}}$و${\displaystyle x_{j}>x_{j+1}}$بافتراض أن${\displaystyle x_{i-1}}$و${\displaystyle x_{j+1}}$موجود. على سبيل المثال إذا${\displaystyle n}$هو عدد طبيعي ، المتتالية${\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle }$لديه الجريتان${\displaystyle \langle n+1,\dots ,2n\rangle }$و${\displaystyle \langle 1,\dots ,n\rangle }$.

يترك${\displaystyle {\mathtt {runs}}(X)}$يُعرَّف بأنه عدد المواضع${\displaystyle i}$بحيث${\displaystyle 1\leq i<n}$و${\displaystyle x_{i+1}<x_{i}}$ويُعرَّف بشكل مكافئ بأنه عدد مرات تشغيل${\displaystyle X}$ناقص واحد. هذا التعريف يضمن أن${\displaystyle {\mathtt {runs}}(\langle 1,2,\dots ,n\rangle )=0}$أي${\displaystyle {\mathtt {runs}}(X)=0}$إذا، وفقط إذا، التسلسل${\displaystyle X}$تم الترتيب. كمثال آخر،${\displaystyle {\mathtt {runs}}(\langle n,n-1,\dots ,1\rangle )=n-1}$و${\displaystyle {\mathtt {runs}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n}$.

الوظيفة${\displaystyle {\mathtt {runs}}}$هو مقياس للفرز المسبق . فرز الدمج الطبيعي هو${\displaystyle {\mathtt {runs}}}$-الأمثل . أي، إذا كان معروفًا أن التسلسل يحتوي على عدد قليل من عمليات التشغيل، فيمكن فرزه بكفاءة باستخدام فرز الدمج الطبيعي.

يُعرَّف التسلسل الطويل بشكل مشابه للتسلسل العادي، باستثناء أن التسلسل قد يكون إما تصاعديًا أو تنازليًا. لا يُعدّ عدد التسلسلات الطويلة مقياسًا للترتيب المسبق. يمكن ترتيب تسلسل يحتوي على عدد قليل من التسلسلات الطويلة بكفاءة عن طريق عكس التسلسلات التنازلية أولًا، ثم استخدام خوارزمية فرز الدمج الطبيعية.

• باورز، ديفيد إم دبليو؛ ماكماهون، غراهام بي. (1983). "مجموعة من برامج برولوج الشيقة". التقرير الفني رقم 8313 (تقرير). قسم علوم الحاسوب، جامعة نيو ساوث ويلز.
• مانيلا، هـ (1985). "مقاييس الفرز المسبق وخوارزميات الفرز الأمثل". معاملات IEEE للحوسبة (C-34): 318-325 . doi : 10.1109/TC.1985.5009382 .