论文标题
在随机排列上流行堆栈排序的运行时间下界限
Lower bound on the running time of Pop-Stack Sorting on a random permutation
论文作者
论文摘要
Pop-stack排序是一种算法，将置换作为输入并分类其元素。它由几个步骤组成。在一步中，该算法读取其必须从左到右处理的排列，并逆转其最大降低连续元素的子序列。它在输出身份置换的第一步终止。 在本说明中，我们回答了在均匀的随机排列$σ_n$上的Pop-stack排序运行时间的防御问题。更确切地说，我们表明存在一个恒定的$ c> 0.5 $，因此几乎可以肯定的是，算法至少需要$ CN $步骤才能在$σ_n$上终止。
Pop-Stack Sorting is an algorithm that takes a permutation as an input and sorts its elements. It consists of several steps. At one step, the algorithm reads the permutation it has to process from left to right and reverses each of its maximal decreasing subsequences of consecutive elements. It terminates at the first step that outputs the identity permutation. In this note, we answer a question of Defant on the running time of Pop-Stack Sorting on the uniform random permutation $σ_n$. More precisely, we show that there is a constant $c > 0.5$ such that asymptotically almost surely, the algorithm needs at least $cn$ steps to terminate on $σ_n$.
