Faster Algorithms for Sorting by Transpositions and Sorting by Block Interchanges

In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity O (n(3/2) root logn). By means of the permutation tree, we can improve this algorithm to achieve time complexity O (nlogn). We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from O (n(2)) down to O (nlogn).

在本文中，我们提出一种新的数据结构，称为排列树，以提高通过对换对排列进行排序以及通过块交换对排列进行排序的运行时间。现有的通过对换对排列进行排序的1.5 - 近似算法具有时间复杂度\(O(n^{\frac{3}{2}}\sqrt{\log n})\)。借助排列树，我们能够改进该算法以实现时间复杂度\(O(n\log n)\)。我们还能够改进通过块交换对排列进行排序的算法，使其时间复杂度从\(O(n^{2})\)降低到\(O(n\log n)\)。