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

辽宁石油化工大学学报 ›› 2007, Vol. 27 ›› Issue (3): 49-52.

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

刘金义

辽宁石油化工大学计算机与通信工程学院，辽宁抚顺 113001

收稿日期:2006-11-07 出版日期:2007-09-20 发布日期:2017-07-23

An Improved Algorithm for the Linear Partition Problem

LIU Jin-yi

School of Computer and Communication Engineering, Liaoning University of Petroleum & Chemical Technology, Fushun Liaoning 113001, P. R. China

Received:2006-11-07 Published:2007-09-20 Online:2017-07-23

摘要/Abstract

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

关键词: 算法, 时间复杂度, 空间复杂度, 线性划分问题

Abstract: Given a sequence X={x1,x2,…,xn} with n non-negative numbers and a positive integer k≤n, the linear partition problem requires to partition X into k or less than k subsequences, so as to minimize the maximum sum of elements over all subsequences. The known best algorithm for this problem is a dynamic programming algorithm with time complexity O(kn2) and space complexity O(kn). By using the properties of the non-negative sequence, an improved algorithm with time complexity O(knlogn) and space complexity O(n) was given.

Key words: Algorithm, Time complexity, Space complexity, Linear partition problem.

刘金义. 线性划分问题的一个改进算法[J]. 辽宁石油化工大学学报, 2007, 27(3): 49-52.

LIU Jin-yi. An Improved Algorithm for the Linear Partition Problem[J]. Journal of Liaoning Petrochemical University, 2007, 27(3): 49-52.

[1]	叶豪杰, 李文娜. 基于PSO的管式加热炉热效率动态矩阵控制[J]. 辽宁石油化工大学学报, 2023, 43(3): 81-85.
[2]	姜楠, 罗林, 王乔, 侯维. 结构优化深度网络的高压断路器机械故障诊断[J]. 辽宁石油化工大学学报, 2023, 43(3): 91-96.
[3]	吴春旭, 贾银山, 于红绯. 一种Apriori算法的高效实现方法及其应用[J]. 辽宁石油化工大学学报, 2023, 43(2): 78-85.
[4]	刘媛杰, 柳强. 一种基于拆卸复杂度的管路敷设顺序优化方法[J]. 辽宁石油化工大学学报, 2023, 43(2): 86-91.
[5]	王伟明, 李文娜. 改进遗传算法优化多偏差控制加热炉支管平衡[J]. 辽宁石油化工大学学报, 2023, 43(1): 73-79.
[6]	那新宇, 余华鹏, 金鑫, 王越. 基于ISSA的多变量ORVFL网络自适应预测控制[J]. 辽宁石油化工大学学报, 2023, 43(1): 80-88.
[7]	刘臻博, 金鑫, 李平. 基于免疫算法结构分解的分布式预测控制算法[J]. 辽宁石油化工大学学报, 2022, 42(5): 90-96.
[8]	张树梅, 高兴军, 邓子龙, 王月. 基于粒子优化算法的并联机器人误差建模分析[J]. 辽宁石油化工大学学报, 2021, 41(5): 79-84.
[9]	卢洋，石元博. 基于向量空间模型的个性化网页搜索算法研究[J]. 辽宁石油化工大学学报, 2021, 41(2): 92-96.
[10]	陶文华，陈娇，桂运金，孔平平. DE算法改进的炼焦能耗RBF预测模型[J]. 辽宁石油化工大学学报, 2020, 40(2): 91-96.
[11]	梁健源，穆克，佀秀杰，王发科. 油扩散泵电磁加热系统的温控研究[J]. 辽宁石油化工大学学报, 2019, 39(5): 93-97.
[12]	赵士龙，李维军，石成江. 基于优化BP神经网络的铝箔封口检测研究[J]. 辽宁石油化工大学学报, 2019, 39(1): 97-100.
[13]	戴璞微,潘斌,王玉铭,朱峰. 一种基于层次分析法的改进KNN算法[J]. 辽宁石油化工大学学报, 2018, 38(04): 87-92.
[14]	尤田,张威,葛琳琳. 基于GA-PSO算法焊接机器人路径规划研究[J]. 辽宁石油化工大学学报, 2018, 38(02): 85-89.
[15]	王志峰, 冯锡炜, 贾强, 朱睿, 秦航. 多特征神经网络微博转发预测[J]. 辽宁石油化工大学学报, 2017, 37(6): 47-50.