• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE/ACM transactions on computational biology and bioinformatics >A New Efficient Algorithm for the All Sorting Reversals Problem with No Bad Components
【24h】

A New Efficient Algorithm for the All Sorting Reversals Problem with No Bad Components

机译：一种无不良成分的全排序逆转问题的高效算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The problem of finding all reversals that take a permutation one step closer to a target permutation is called the all sorting reversals problem (the ASR problem). For this problem, Siepel had an O(n 3)-time algorithm. Most complications of his algorithm stem from some peculiar structures called bad components. Since bad components are very rare in both real and simulated data, it is practical to study the ASR problem with no bad components. For the ASR problem with no bad components, Swenson et al. gave an O (n2)-time algorithm. Very recently, Swenson found that their algorithm does not always work. In this paper, a new algorithm is presented for the ASR problem with no bad components. The time complexity is O(n2) in the worst case and is linear in the size of input and output in practice.
机译：查找将排列与目标排列更接近一步的所有冲销的问题称为所有排序冲销问题（ASR问题）。对于这个问题，Siepel有一个O（n 3）时间算法。他的算法的大多数复杂性源于一些称为不良组件的特殊结构。由于在实际和模拟数据中不良成分都很罕见，因此研究无不良成分的ASR问题是可行的。对于没有不良组件的ASR问题，Swenson等人。给出了O（n2）时间算法。最近，Swenson发现他们的算法并不总是有效。在本文中，提出了一种新的无不良组件问题的算法。在最坏的情况下，时间复杂度为O（n2），实际上输入和输出的大小是线性的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号