シーケンスの実行

コンピュータ サイエンスでは、シーケンスのランとは、拡張できないシーケンスの非減少範囲です。シーケンスのランの数は、シーケンスの増加サブシーケンスの数です。これは、事前ソートの尺度であり、特にシーケンスをソートするためにマージする必要があるサブシーケンスの数を測定します。

を全順序集合の要素のシーケンスとします。のランは最大増加シーケンスです。つまり、および^{[説明が必要]}が存在すると仮定します。たとえば、が自然数の場合、シーケンスにはおよび の2 つのランがあります。 ${\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 }$

を、およびとなる位置の数として定義します。これは、マイナス 1 の連続数として定義されることと同等です。この定義により、シーケンスがソートされている場合に限り、つまり が保証されます。別の例として、および があります。 ${\displaystyle {\mathtt {runs}}(X)}$${\displaystyle i}$${\displaystyle 1\leq i<n}$${\displaystyle x_{i+1}$${\displaystyle X}$${\displaystyle {\mathtt {実行数}}(\langle 1,2,\dots ,n\rangle )=0}$${\displaystyle {\mathtt {runs}}(X)=0}$${\displaystyle X}$${\displaystyle {\mathtt {実行数}}(\langle n,n-1,\dots ,1\rangle )=n-1}$${\displaystyle {\mathtt {実行数}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n}$

この関数は、事前ソートの尺度です。自然マージソートは r u n s {\displaystyle {\mathtt {runs}}} 最適です。つまり、シーケンスの実行回数が少ないことがわかっている場合は、自然マージソートを使用して効率的にソートできます。 ${\displaystyle {\mathtt {実行}}}$

ロングランはランと同様に定義されますが、シーケンスが非減少または非増加のいずれかになる点が異なります。ロング ランの数は、事前ソートの尺度ではありません。ロング ランの数が少ないシーケンスは、最初に減少ランを逆にしてから、自然マージ ソートを使用することで、効率的にソートできます。

• Powers, David MW; McMahon, Graham B. (1983)。「興味深い Prolog プログラムの概要」。DCS 技術レポート 8313 (レポート)。ニューサウスウェールズ大学、コンピュータサイエンス学部。
• Mannila, H (1985). 「事前ソートの尺度と最適ソートアルゴリズム」IEEE Trans. Comput. (C-34): 318–325. doi :10.1109/TC.1985.5009382.