...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Hadronic Journal >THE RELATIONSHIP BETWEEN BALANCE AND THE SPEED OF ALGORITHMS
【24h】

THE RELATIONSHIP BETWEEN BALANCE AND THE SPEED OF ALGORITHMS

机译：平衡与算法速度之间的关系

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

摘要

It is argued in [AHU83] that Divide & Conquer techniques which make a "balanced" division lead to faster algorithms. We investigate the use of the imbalance lattice of [PR99] in the context of path-length sequences for decision trees of sorting algorithms. This forms a novel exploration of this lattice which prior to this has been restricted to the study of balance of trees, independently from running time. In this way we obtain a link between the balance of the decision tree of an algorithm and the speed of the algorithm. We use the imbalance lattice of [PR99] in the following to put this intuition on a formal basis. We will use the imbalance lattice to show that mergesort has a better running time than insertion sort due to the fact that its decision tree is more balanced than that of insertion sort. We extend the imbalance lattice with an algebraic operation. This operation corresponds to the extension of a binary tree with new binary trees at the leafs, which reflects the effect of recursive calls of an algorithm on the decision tree. Finally, we also introduce a new representation for binary trees which enables us to represent the binary tree for mergesort in an inductive way.
机译：[AHU83]指出，采用“均衡”划分的分而治之技术可带来更快的算法。我们研究在路径长度序列的上下文中使用[PR99]的不平衡晶格进行排序算法的决策树。这形成了对该晶格的新颖探索，在此之前，与运行时间无关，该晶格仅限于研究树木的平衡。这样，我们获得了算法的决策树平衡与算法速度之间的联系。下面我们使用[PR99]的不平衡格将这种直觉形式化。我们将使用不平衡格来显示归并排序比插入排序具有更好的运行时间，这是因为其决策树比插入排序的决策树更均衡。我们通过代数运算来扩展不平衡晶格。此操作对应于在叶子处具有新的二叉树的二叉树的扩展，这反映了决策树上算法的递归调用的效果。最后，我们还为二叉树引入了一种新的表示形式，使我们能够以归纳方式表示用于mergesort的二叉树。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号