问题标签 [divide-and-conquer]

我正在尝试通过使用 FFT 的分治算法来评估多项式 A(x)。我基本上将多项式分解为奇数根和偶数根，然后在两个较小的多项式上递归。（允许我每次递归计算两倍的数值）。

为了可视化这一点，我试图创建一棵树来显示多项式在算法中的路径。我不确定如何开始——有人可以让我开始吗？我不期望一棵完整的树只是一个让我走上正确道路的简短示例。

实现一个特定的排序算法，我遇到了一个问题，即使谷歌不想帮助我......首先是关于算法的一些话：

最大的份额是将输入（数组）划分为三个部分：选择两个关键数字（红色和蓝色，断言红色 <= 蓝色），分区的元素将（1）小于两者，（2）在某处在和 (3) 之间大于两个枢轴。这是工作正常的部分！

对数组进行排序应该递归地进行：在对其分区进行分区之前使用任意枢轴对输入进行分区，从而以长度为 1 或 2 的粒子结束，这些粒子按 def 排序。或者说可以很容易地排序。

现在的问题是长度 >= 3 的分区由一个键值组成：如果再次分区，无论选择什么枢轴，之后所有元素都会放入同一个分区，最终导致堆栈溢出。这就是为什么我认为你能够帮助我，因为我确信有一个解决方案。

强制性 JavaCode 片段：分区 - 对德语调试感到抱歉，也懒得翻译它。IntTuple 只能容纳两个整数；没什么太荒谬的。

强制 JavaCode 片段：排序

非常感谢您的任何想法！

问候， LDer

更多：我想出了这个 hacky 和尴尬的解决方案：

任何人都可以帮助创建一个更具可读性的版本吗？

更多：这个看起来好多了：

特别感谢 toto2，即使我没有明确通过红色/蓝色！

更多：更多随机性，因为 toto2 再次完全有一点：

我正在制作一个实现合并排序算法的程序，但不是每次将它们分成两部分，而是每次将它们分成三部分并递归地对它们进行合并排序。万一我把你弄糊涂了，它基本上是一个归并排序，但不是用 2 个部分归并排序，而是每次归并排序 3，听起来很有趣吧？那么它绝对不是。

这是我的合并排序实现：

这是合并方法：

在合并方法内部的评论中，我尝试制作另一种合并方法，但结果并不好，事情变得更加复杂，但我把它留在那里以供参考。

问题是这根本不起作用，例如，如果我有：

输入：6 5 4 3 2 1

然后我会有：

输出：[2、1、4、3、6、5]

老实说，我为此非常努力，连续 2 天，我发现只有两个人甚至听说过这种合并排序，在谷歌搜索数小时后，我在这里只发现了一个类似的问题（这太复杂了，难以理解）和另一个线程在从未回答过的维基答案中。

任何帮助将不胜感激，当然我不是要求直接解决方案，因为我正在努力学习，但是提示和提示以及我做错了什么会对我有很大帮助。

提前致谢。

我正在尝试使用分治法实现以下算法，以使运行时间达到 O(n*logn)。

给定一个数字序列 a_1、a_2、...、a_n 和一个数字 k，找到 i 和 j 使得 1<= j – i <= k，同时最大化 a_i + a_j。

例如对于序列 10,2,0,8,1,7,1,0,11 和 k = 2，最大值为 15 = 8 + 7。

我已经实现了某种分而治之的方法，但我正在努力弄清楚如何检查跨越每个分界间隔的值。这是我到目前为止所拥有的：

我认为我在正确的轨道上，我只是在努力弄清楚如何合并跨越两个间隔的数字的校验和，而不使用会产生 O(n^ 2) 复杂性。

如果有任何关于如何继续此操作的指示或提示，将不胜感激。另外，我目前正在假设数组中有偶数个整数。多谢你们。

我正在使用“算法简介”中描述的算法来实现 Mergesort。但是，每次执行时，我都会得到一个垃圾值作为排序数组的第一个元素。这是它的代码：

我正在尝试制作二进制搜索的分而治之版本，但是将数组划分为两个子数组并进行搜索类似于合并排序中的合并，我想这样做的原因是我想在 cilk 中使用它，但是我必须这样做。这是我编写的代码，它似乎有问题，因为它返回 -1 到有效的键值。

为什么分而治之的算法通常比蛮力运行得更快？例如，查找最近的一对点。我知道你可以给我看数学证明。但直觉上，为什么会发生这种情况？魔法？

从理论上讲，“分而治之总是胜于蛮力”是真的吗？如果不是，有反例吗？

我需要有关如何获得某个数字的第 n 个根的帮助。

用户输入数字 n 和他想要根的数字。我需要在没有 cmath 库的情况下使用分而治之的方法来解决这个问题。

这是我的代码还不能工作：

关于如何解决这个问题的任何想法都将非常有用。

我一直在关注 Coursera 的算法课程，并想出了一个关于最近配对问题的分/治算法的想法，我想澄清一下。

根据 Roughgarden 教授的算法（如果您有兴趣，可以在此处查看）：对于给定的一组点 P，我们有两个副本 - 在 X 和 Y 方向上排序 - Px 和 Py，算法可以给出为

最接近对（Px，Py）：

1. 将点分成左半部分 - Q 和右半部分 - R，并沿 x 和 y 方向形成两半的排序副本 - Qx,Qy,Rx,Ry
2. 让closestPair(Qx,Qy)为点p1和q1
3. 设最接近对(Rx,Ry)为p2,q2
4. 令 delta 为 dist(p1,q1) 和 dist(p2,q2) 的最小值
5. 这是不幸的情况，让 p3,q3 成为最接近的SplitPair(Px,Py,delta)
6. 返回最好的结果

现在，我想要的澄清与第 5 步有关。我应该事先说一下，我的建议几乎没有任何改进，但如果你仍然感兴趣，请继续阅读。

R 教授说，由于点已经在 X 和 Y 方向上排序，为了在步骤 5 中找到最佳对，我们需要迭代宽度为 2*delta 的条带中的点，从下到上，在内部循环我们只需要 7 个比较。这可以改善到只有一个吗？

我觉得怎么可能用纯文本解释起来有点困难，所以我画了一张图，写在纸上，然后上传到这里：

由于没有其他人想出是，我很确定我的思路有一些错误。但我现在已经想了好几个小时了，我只好发布这个。这就是我脑子里的一切。

有人可以指出我哪里出错了吗？

想分析递归线性搜索的复杂性（使用分治技术）。是 log(n) 还是 n ？如果不是 log(n) 那么实际复杂性是多少以及如何？