返回整卷
BOK 数据结构
数据结构

2016-43

综合题15 分

已知由 n(n≥2)个正整数构成的集合 A={ak| 0≤ k<n},将其划分为两个不相交的子集 A1 和 A2,元素个数分别是 n1 和 n2,A1 和 A2 中元素之和分别为 S1 和 S2。设计一个尽可能高效的划分算法,满足 |n1-n2| 最小且 |S1-S2| 最大。要求:
(1)给出算法的基本设计思想。

(2)根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。

(3)说明你所设计算法的平均时间复杂度和空间复杂度。