高德纳书中一道很普通的题目

liangbch

回楼上，这种算法所需的运算次数为不是$2^25+2^25=2^26$, 而是$2^25*log2(2^25)=25*2^25$,对于表一中的每个数，需要在表2中使用2分查找算法查找最合适的那个数。
  另外排序的所花的时间也不得不考虑。这部分的复杂度和查找表的算法相当。

  关于空间复杂度。
  这种做法的内存耗费很大。表中的每项目需要1个DWORD(bit数组，表示某个组合包含哪些数)+1个Double,共需 2×$2^25$×(4+8)=800M内存,如果超过54个数，总的内存需求球超过3G,那时就需要使用磁盘做缓冲，速度将会大大下降。

KeyTo9_Fans

确实如此。

可是Fans不想就此罢休。

首先列表$1$中有

$0$

把$\sqrt(1)$加进来，得到

$0$
$\sqrt(1)$

把$\sqrt(2)$加进来，得到

$0$
$\sqrt(1)$
$\sqrt(2)$
$\sqrt(1)+\sqrt(2)$

把$\sqrt(3)$加进来，得到

$0$
$\sqrt(1)$
$\sqrt(2)$
$\sqrt(3)$
$\sqrt(1)+\sqrt(2)$
$\sqrt(1)+\sqrt(3)$
$\sqrt(2)+\sqrt(3)$
$\sqrt(1)+\sqrt(2)+\sqrt(3)$

每加一个数，就相当于把两张长度相同的表合并成一张表。

例如，当把$\sqrt(4)$加进来时，就相当于合并

$0$
$\sqrt(1)$
$\sqrt(2)$
$\sqrt(3)$
$\sqrt(1)+\sqrt(2)$
$\sqrt(1)+\sqrt(3)$
$\sqrt(2)+\sqrt(3)$
$\sqrt(1)+\sqrt(2)+\sqrt(3)$

与

$0+\sqrt(4)$
$\sqrt(1)+\sqrt(4)$
$\sqrt(2)+\sqrt(4)$
$\sqrt(3)+\sqrt(4)$
$\sqrt(1)+\sqrt(2)+\sqrt(4)$
$\sqrt(1)+\sqrt(3)+\sqrt(4)$
$\sqrt(2)+\sqrt(3)+\sqrt(4)$
$\sqrt(1)+\sqrt(2)+\sqrt(3)+\sqrt(4)$

这两张表。

很显然地，这个合并操作的时间复杂度为$O(n)$，其中$n$是列表长度。

我们从$\sqrt(1)$一直合并到$\sqrt(25)$，所需操作次数为

$2+4+8+16+...+2^26$ ~= $2^27$

相当于常数因子大了一点，但仍然是$O(n)$的复杂度，其中$n$是列表长度。

制作列表$2$的操作步骤完全相同。

好了，现在把$3$楼的最后一句话说得更清楚一点：

当列表$1$从前往后取数的时候，

要保持其和最接近但不超过总和的一半，

那么列表$2$一定是从后往前取数的。

所以这部分操作的时间复杂度也是$O(n)$的，其中$n$是列表长度。

综上所述，整个算法的时间复杂度是$O(n)$的。

虽然常数因子有点大，但总比$O(n*log(n))$好。

关于空间复杂度的问题……

分段制作列表如何？

比如先制作列表$1$的前$1/4$和列表$2$的后$1/4$。

然后列表$1$从前往后取数，列表$2$从后往前取数。

哪张表的数取完了，就可以清空列表，制作下一段$1/4$。

不知道这种节省空间的做法是否需要牺牲时间来换取。

mathe

呵呵，Fans的方法不错。
我想到的是medie2005类似的方法，当然量化因子要扩大，此外没有必要使用求模运算。然后通过使用正向和逆向动态规划过滤一些模式。
而Fans的方法也可以结合数据量化

KeyTo9_Fans

确实如此。

不过Fans不想把数据存成double类型。

因为double类型里面有一部分比特位是用来记录科学记数法中的指数的。

而在这个问题中，所用到的数据的数量级基本一致。

所以没有必要记录科学记数法中的指数。

所以我们用64位整数(unsigned long long)类型来表示$\sqrt(1)$、$\sqrt(2)$、$\sqrt(3)$、...、$\sqrt(50)$。

这样不仅可以提高精确程度，而且可以提高运算速度。

mathe

呵呵，量化后一个更大的好处是可以采用位图来存储数据，节省内存呀

gxqcn

14# KeyTo9_Fans

也没必要用64bit的整数，用32bit的整数足矣。

可取量化因子 $k=|__(2^32-1)/(\sum_{i=1}^{50}{\sqrt{i}-1})__|=22720390$
即将每个平方根 $\sqrt{i}$ 对应于 $k(\sqrt{i}-1)$ 向下取整即可，
在相加过程中不会出现溢出情况，且该量化因子足矣拉开差距，保证精度。

medie2005

呵呵，Fans的方法不错。
我想到的是medie2005类似的方法，当然量化因子要扩大，此外没有必要使用求模运算。然后通过使用正向和逆向动态规划过滤一些模式。
而Fans的方法也可以结合数据量化
mathe 发表于 2010-3-25 07:28

我觉得我的方法没问题啊。
逆向动态规划？不明白。
还有你说的

50个数中部分和有$2^50$中情况，所以平均来看应该存在一组数，同正好一半的误差小于$239/{2^50}$
所以上面的方法还远远不够
mathe 发表于 2010-3-24 18:35

$239/{2^50}$怎么来的？

KeyTo9_Fans

16# gxqcn

Fans觉得$32$bit不够用啊。

看来mathe大师的精神也很难领会呢

因为在$\sqrt(1)$、$\sqrt(2)$、$\sqrt(3)$、...、$\sqrt(50)$中，取其子集，有$2^50$种取法。

每种取法对应一个和。

这$2^50$个和都在$0$到$239$之间。

我们假设它们均匀分布在区间$[0,239]$中。

于是在$118$附近，每隔$239/2^50$的长度就有一个数。

所以我们至少需要$50$个bit来区分它们。

不知道mathe大师是不是这样想的。

而郭大师认为$32$个bit是足够的。

这个精神境界比mathe大师的境界高。

Fans暂时没能领会。

不知道mathe大师能否领会呢？

gxqcn

我没有细读你们的算法，有点断章取义了，抱歉。

mathe

总体上来说，我觉得用Fans的方法比较好。现在唯一的问题就是空间复杂度有点大。
我原先想的方法还是medie2005的方法，只是我觉得量化的范围需要更加大一些，要不然过滤以后需要穷举的解还是太多了。
显然，总体数据如果用50比特来表示，空间复杂度是一个大问题，所以我们可以将整个过程分成两步，第一步用动态规划进行过滤，第二步利用第一步结果对搜索过程进行裁剪。
于是第一步我们可以将所有数据进行量化，只取比如前面28比特数据，比如小数点前8比特，小数点后20比特，余下部分采用四舍五入法，所以不超过50个数据累加后误差最多为正负25.
而由于只取28比特，假设量化后50个数总和为2M;可以预计，结果等于M的子数组必然会取到；但是由于误差存在，我们需要搜索所有和的结果在M-25和M+25之间的子数组。
由此，我们先采用动态规划，计算出前k个数的部分和可以到达的位图（如果全部保存，需要内存${50*2^28}/8~=1.7G$,但是我们可以只保存中间的若干个位图，从而可以大量节省内存）。
此后，有了这些位图，我们可以再次通过反向使用这些结果，计算后面k个数据之和加上某些50-k个前面数据之和在M-25和M+25之间的方案，对这些方案进行搜索并求出浮点值最优的方案。

而我说的结果Fans和量化的方法基本类似，就是先求出所有前25个数据部分和并且量化到比如28比特。
然后对每个后25个数据的所有部分和进行穷举，对于每个和，如果它可以和某个前面25个数据的部分和到达最优值，我们直接可以估算出前面那个部分和量化以后的结果应该是在某个范围。而由于对于每个指定的量化数据，正好落在那个范围的前25个数据部分和的数据量会非常至少（按概率，平均小于1），我们逐个检查那些落在这个范围的数据就可以了