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

辽宁石油化工大学学报 ›› 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]	王瑶, 张孟航, 王伟, 王进. 基于ISSA⁃ELM模型的温室环境参数预测研究[J]. 辽宁石油化工大学学报, 2024, 44(4): 75-81.
[2]	安世硕, 高海, 李维军, 唐静, 张文才. 基于改进鲸鱼算法的收卷张力PID控制的性能优化[J]. 辽宁石油化工大学学报, 2024, 44(4): 91-96.
[3]	焦园娜, 左振华, 张雷雷, 郭志恒, 阚哲. 基于带约束粒子群的电容层析成像图像重建算法[J]. 辽宁石油化工大学学报, 2024, 44(2): 91-96.
[4]	常万杰, 刘琳琳, 曹宇, 曹杨, 魏海平. 基于Informer算法的病毒传播预测研究[J]. 辽宁石油化工大学学报, 2024, 44(1): 80-88.
[5]	赵丽洲, 张宁峰. 双循环背景下石化企业供应链韧性评价研究[J]. 辽宁石油化工大学学报, 2024, 44(1): 89-96.
[6]	叶豪杰, 李文娜. 基于PSO的管式加热炉热效率动态矩阵控制[J]. 辽宁石油化工大学学报, 2023, 43(3): 81-85.
[7]	姜楠, 罗林, 王乔, 侯维. 结构优化深度网络的高压断路器机械故障诊断[J]. 辽宁石油化工大学学报, 2023, 43(3): 91-96.
[8]	吴春旭, 贾银山, 于红绯. 一种Apriori算法的高效实现方法及其应用[J]. 辽宁石油化工大学学报, 2023, 43(2): 78-85.
[9]	刘媛杰, 柳强. 一种基于拆卸复杂度的管路敷设顺序优化方法[J]. 辽宁石油化工大学学报, 2023, 43(2): 86-91.
[10]	王伟明, 李文娜. 改进遗传算法优化多偏差控制加热炉支管平衡[J]. 辽宁石油化工大学学报, 2023, 43(1): 73-79.
[11]	那新宇, 余华鹏, 金鑫, 王越. 基于ISSA的多变量ORVFL网络自适应预测控制[J]. 辽宁石油化工大学学报, 2023, 43(1): 80-88.
[12]	刘臻博, 金鑫, 李平. 基于免疫算法结构分解的分布式预测控制算法[J]. 辽宁石油化工大学学报, 2022, 42(5): 90-96.
[13]	张树梅, 高兴军, 邓子龙, 王月. 基于粒子优化算法的并联机器人误差建模分析[J]. 辽宁石油化工大学学报, 2021, 41(5): 79-84.
[14]	卢洋，石元博. 基于向量空间模型的个性化网页搜索算法研究[J]. 辽宁石油化工大学学报, 2021, 41(2): 92-96.
[15]	陶文华，陈娇，桂运金，孔平平. DE算法改进的炼焦能耗RBF预测模型[J]. 辽宁石油化工大学学报, 2020, 40(2): 91-96.