线性划分问题的一个改进算法

• 作者: 刘金义
• 来源期刊: 辽宁石油化工大学学报
• 学科: 工学
• 关键词: 算法 时间复杂度 空间复杂度 线性划分问题
• 年，卷（期）: 2007,（3）
• 所属期刊栏目: 计算机与自动化
• 页码范围: 49-52
• 页数: 4页
• 分类号: TP314
• 字数: 3723字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-6952.2007.03.015

摘要

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值.目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法.利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘金义	辽宁石油化工大学计算机与通信工程学院	21	318	5.0	17.0