Spa*_*dan 2 c++ algorithm performance implementation
标准子集和问题的一个小变化是我们想要从一组N大小中找到K大小的子集,其总和达到S.
标准的蛮力解决方案产生复杂度O(N ^ K).但是,上面的链接提到了一种蛮力方法的变化,复杂度为O(N ^(K/2)).
维基文章说
已知更好的指数时间算法,其在时间O(2N/2)中运行.该算法任意地将N个元素分成两组N/2.对于这两组中的每一组,它存储其元素的所有2N/2个可能子集的总和的列表.然后对这两个列表中的每一个进行排序.对该步骤使用标准比较排序算法将花费时间O(2N/2N).但是,给定k个元素的和的排序列表,可以通过引入(k + 1)st元素将列表扩展为两个排序列表,并且可以在时间O(2k)中合并这两个排序列表.因此,每个列表可以在时间O(2N/2)中以排序的形式生成.给定两个排序列表,该算法可以检查第一阵列的元素和第二阵列的元素是否在时间O(2N/2)中总和.为此,算法按递减顺序(从最大元素开始)和第二个数组按递增顺序(从最小元素开始)通过第一个数组.只要第一个数组中的当前元素和第二个数组中的当前元素之和大于s,算法就会移动到第一个数组中的下一个元素.如果它小于s,则算法移动到第二个数组中的下一个元素.如果找到两个带有sum的元素,它就会停止.
现在基本上它说如果我们想要找到大小为k的子集,我们计算n个散列大小为K/2的所有子集及其SUM,其中sum是散列中的关键.然后检查是否有两组大小(k)/2)总结到S.
我理解算法,但无法弄清楚,我们怎样才能实现它.散列整数(Sum),其值为列表元组,其中包含实际集合的(K/2)索引.
我们如何在C++中有效地实现它.使用Data sturctures？由于大小(k/2)元素的和,可以并且将是非唯一的,我们不能使用MAP,我们需要多地图,或类似的东西.