标签: divide-and-conquer

Divide和Conquer算法和动态规划算法有什么区别？这两个术语有何不同？我不明白他们之间的区别.

请举一个简单的例子来解释两者之间的差异以及它们看起来相似的基础.

如何最优地将数组划分为两个子数组,以使两个子数组中的元素总和相同,否则会出错？

例1

鉴于阵列

10,  20 , 30 , 5 , 40 , 50 , 40 , 15

它可以分为

10, 20, 30, 5, 40

和

50, 40, 15

每个子阵列总计达105.

例2

10,  20,  30,  5,  40,  50,  40,  10

该数组不能分为2个等数和的数组.

我被问到二元搜索是否是考试中的分而治之算法.我的回答是肯定的,因为你将问题分成了较小的子问题,直到你达到了结果.

但是检查员询问其中的征服部分在哪里,我无法回答.他们也不赞成它实际上是一种分而治之的算法.

但是我到网上的所有地方都说它是,所以我想知道为什么,以及征服它的部分在哪里？

我正在尝试使用分而治之算法来混合链表,该算法随后在线性(n log n)时间和对数(log n)额外空间中随机混洗链表.

我知道我可以做一个类似于可以在一个简单的数组中使用的Knuth shuffle,但是我不知道如何用分而治之的方式做到这一点.我的意思是,我实际上分裂了什么？我只是划分到列表中的每个单独节点,然后使用一些随机值将列表随机组合在一起？

或者我给每个节点一个随机数,然后根据随机数在节点上进行合并？

为什么分而治之的算法通常比蛮力运行得更快？例如,找到最接近的一对点.我知道你可以告诉我数学证明.但直觉上,为什么会这样呢？魔法？

从理论上说,"分而治之总是比蛮力更好"吗？如果不是,是否有任何反例？

在我的算法与数据结构类第一divide-and-conquer algorithm,即merge sort进行了介绍.

在为分配实现算法时,我想到了一些问题.

1. 使用除法和征服范式实现的算法是否具有O(nlogn)的时间复杂度？

2. 是否该方法中的递归部分能够压缩以O(n ^ 2)到O(nlogn)运行的算法？

3. 是什么让这种算法首先在O(nlogn)中运行.

对于(3)我假设这与递归树和可能的递归数量有关.有人可能会用一个简单的分而治之算法来运行,该算法在O(nlogn)中运行如何实际计算复杂度？

干杯,安德鲁

我正在编写一个合并排序函数,现在我只使用一个测试用例数组(没有输入 - 这是静态的,现在).我不知道如何将数组作为参数传递.这是我现在的代码:

//merge sort first attempt

#include <iostream>

#include <algorithm>

#include <vector>

int mergeSort(int[]);
int main() {
    int originalarray[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 };
    mergeSort(originalarray[]);
}

int mergeSort(int[] originalarray) {
    int num = (sizeof(originalarray) / sizeof(int));
    std::vector < int > original(num);

    if (num > 2) {
        return num;
    }

    // Fill the array using the elements of originalarray
    // This is just for demonstration, normally original will be a parameter,
    // …

更新:我添加了这个问题的答案,其中包含了几乎所有已经给出的建议.下面代码中给出的原始模板需要45605ms才能完成真实世界的输入文档(关于脚本编程的英文文本).社区维基回答中的修订模板将运行时间降至605毫秒!

我正在使用以下XSLT模板将字符串中的一些特殊字符替换为其转义变体; 它使用分而治之的策略递归调用自己,最终查看给定字符串中的每个字符.然后它决定是否应该按原样打印字符,或者是否需要任何形式的转义:

<xsl:template name="escape-text">
<xsl:param name="s" select="."/>
<xsl:param name="len" select="string-length($s)"/>
<xsl:choose>
    <xsl:when test="$len >= 2">
        <xsl:variable name="halflen" select="round($len div 2)"/>
        <xsl:variable name="left">
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, 1, $halflen)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
        </xsl:variable>
        <xsl:variable name="right">
            <xsl:call-template name="escape-text">
                <xsl:with-param name="s" select="substring($s, $halflen + 1)"/>
                <xsl:with-param name="len" select="$halflen"/>
            </xsl:call-template>
        </xsl:variable>
        <xsl:value-of select="concat($left, $right)"/>
    </xsl:when>
    <xsl:otherwise>
        <xsl:choose>
            <xsl:when test="$s = '&quot;'">
                <xsl:text>&quot;\&quot;&quot;</xsl:text>
            </xsl:when>
            <xsl:when test="$s = '@'">
                <xsl:text>&quot;@&quot;</xsl:text>
            </xsl:when>
            <xsl:when …

我正在寻找一种有效的算法来计算任何给定整数的乘法分区.例如,12的这种分区的数量是4,即

12 = 12×1 = 4×3 = 2×2×3 = 2×6

我已经阅读了维基百科文章,但这并没有真正给我一个生成分区的算法(它只讨论了这些分区的数量,说实话,即使这对我来说也不是很清楚!) .

我正在看的问题要求我为非常大的数字(> 10亿)计算乘法分区,所以我试图为它提出一种动态编程方法(以便找到所有可能的分区,用于较小的数字可以是当较小的数字本身是一个较大数字的因素时重复使用),但到目前为止,我不知道从哪里开始!

任何想法/提示将不胜感激 - 这不是一个家庭作业问题,只是我试图解决的问题,因为它看起来很有趣!

我想知道分而治之的技术总是把问题分成同类型的子问题吗？同一类型,我的意思是可以使用递归函数实现它.可以通过递归来实现分而治之吗？

谢谢!