子问题平衡对合并排序时间复杂性的影响
DOI:
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


The Influence of the Balance of Subproblem on Time Complexity of Merge Sorting
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    利用分治法(divide and conquer)来设计算法时,人们出于平衡的考虑,总是把问题分成相等的子问题递归地分治下去。在很多具体问题上可证明子问题平衡对时问复杂性的常系数可以有改进。本文从合并排序方面讨论证明子问题平衡可使时间复杂性最小。

    Abstract:

    When people design algorithm with the divide and conguer method, out of the consideration of balancing, they always divide the problem into equivalent subproblems recursively. In many practical problems it is proved that the coefficient of time complexity can be improved by balancing the size of the subproblem. This paper is intended to deal with the problem and prove it in terms of merge sorting.

    参考文献
    相似文献
    引证文献
引用本文

顾立尧.子问题平衡对合并排序时间复杂性的影响[J].上海理工大学学报,1988,(3).

复制
分享
相关视频

文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码