Выполнение последовательности

Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Июнь 2021 г. ) ( Узнайте, как и когда удалить это сообщение )

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Материалы без источников могут быть оспорены и удалены. Найти источники:  «Run of a sequence» – новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2021 г. ) ( Узнайте, как и когда удалять это сообщение )

В информатике , пробег последовательности — это неубывающая область последовательности, которая не может быть расширена. Количество пробегов последовательности — это количество увеличивающихся подпоследовательностей последовательности. Это мера предварительной сортировки, и в частности измеряет, сколько подпоследовательностей необходимо объединить для сортировки последовательности.

Пусть будет последовательностью элементов из полностью упорядоченного множества . Серия из является максимальной возрастающей последовательностью . То есть, и ^{[ необходимо разъяснение ]} предполагая, что и существует. Например, если является натуральным числом , последовательность имеет две серии и .${\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 {работает}}(X)}$${\displaystyle я}$${\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}$

Функция является мерой предсортированности. Естественная сортировка слиянием является r u n s {\displaystyle {\mathtt {runs}}} -оптимальной. То есть, если известно, что последовательность имеет небольшое количество запусков, ее можно эффективно отсортировать с помощью естественной сортировки слиянием.${\displaystyle {\mathtt {работает}}}$

Длинный прогон определяется аналогично прогону, за исключением того, что последовательность может быть как неубывающей, так и невозрастающей. Количество длинных прогонов не является мерой предварительной сортировки. Последовательность с небольшим количеством длинных прогонов можно эффективно отсортировать, сначала обратив убывающие прогоны, а затем используя естественную сортировку слиянием.

• Powers, David MW; McMahon, Graham B. (1983). "Сборник интересных программ на прологе". DCS Technical Report 8313 (Report). Кафедра компьютерных наук, Университет Нового Южного Уэльса.
• Маннила, Х (1985). «Меры предварительной сортировки и оптимальные алгоритмы сортировки». IEEE Trans. Comput. (C-34): 318– 325. doi :10.1109/TC.1985.5009382.