问题标签 [divide-and-conquer]

可能重复：
Java：通过多线程并行化快速排序

我真的很抱歉我在这里提出了不好的问题，所以我不想重复我的错误。我发现那里的文章说如何在分而治之算法中实现并行性。多线程是使用 Parallel.Invoke 方法实现的。所以问题是如何在 Java 中实现这种语法并优化线程与 CPU 一起工作

这里我有 C# 中的示例

在Java中

以下问题取自Problems on Algorithms (Problem 653)：

你得到一个数字矩阵。找到一个 O(n log n) 算法，该算法对数组中的行进行置换，使得数组的任何一列都不包含比 ⌈√n 长的递增子序列（可能不包含连续的数组元素）。⌉

我不知道如何解决这个问题。我认为它可能会使用某种分而治之的重复，但我似乎找不到。

有谁知道如何解决这个问题？

给定一个数组，使其元素的值从第 0 个索引增加到某个 ( k -1) 索引。在k处，该值最小，然后通过第n个元素再次开始增加。找到最小元素。

本质上，它的一个排序列表附加到另一个列表；示例：（1、2、3、4、0、1、2、3 ）。

我尝试了各种算法，例如构建最小堆、快速选择或只是简单的遍历。但不能低于 O(n)。但是这个数组中有一个模式，表明二进制搜索类型的东西应该是可能的，复杂性应该是 O(log n) 之类的东西，但找不到任何东西。想法？？

谢谢

我正在尝试解决 T(n) = 2T(n/2) + log n

替换 n = 2^k

所以基本上我需要对 i*2^i 的一项求和，其中 i = 1 以记录 n - 1。
我找不到一种简单的方法来总结这些项。难道我做错了什么 ？有没有其他方法可以解决这个递归？掌握定理对她有用吗？如果是，比如何？

谢谢。

我在寻找解决问题的方法时遇到了一个非常大的问题。我必须创建一个递归的分治算法，该算法计算整数数组中元素的最长非递减子序列的长度。我有以下代码，但它并没有真正起作用，任何帮助将不胜感激！！！

我正在解决练习测验并遇到以下问题

写下与以下分治算法相对应的递归，准确地标记每个组件：划分、征服和组合。

我试图回答。

1. 让 T(n) 是 Foo 在 p 到 r 上所做的工作，所以 T(n) 等价于 Foo(p, r)，其中 n 是 r - p + 1。

2. 我得到以下递归 T(n) = T(n - 1) + Θ(n) + Θ(1)

3. 除法部分将是一个常数 Θ(1)，它对应于 r-1 操作。

4. 征服部分将是递归解决子问题的 T(n - 1)。

5. 组合部分是 T(n - 1) * s 的乘法运算的常数 Θ(1)。

但这似乎是错误的，因为我没有提到 Θ(n)。第 6,7 行的 Θ(n) 应该属于划分、征服、组合的哪一部分？

我正在尝试为树编写分而治之的算法。对于除法步骤，我需要一种算法，通过删除一个节点将给定的无向图 G=(V,E) 与 n 个节点和 m 个边分割成子树。所有子图都应具有不包含超过n/2个节点的属性（树应尽可能相等地拆分）。首先我尝试递归地从树中删除所有叶子以找到最后一个剩余节点，然后我尝试找到 G 中最长的路径并删除它的中间节点。下图显示这两种方法都不起作用：

是否有一些工作算法可以满足我的要求（在上述情况下返回节点 H）。

我正在寻找一种有效的算法来计算任何给定整数的乘法分区。例如，12 的此类分区数为 4，即

12 = 12 x 1 = 4 x 3 = 2 x 2 x 3 = 2 x 6

我已经为此阅读了维基百科文章，但这并没有真正为我提供生成分区的算法（它只讨论了此类分区的数量，老实说，即使这对我来说也不是很清楚！） .

我正在研究的问题需要我为非常大的数字（> 10 亿）计算乘法分区，所以我试图为它想出一种动态编程方法（以便为较小的数字找到所有可能的分区当较小的数字本身是较大数字的一个因素时重新使用），但到目前为止，我不知道从哪里开始！

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

您能否帮助我理解分治算法的时间复杂度。

让我们以这个为例。 http://www.geeksforgeeks.org/archives/4583方法2：它给了T(n) = 3/2n -2，我不明白为什么？

对不起，如果我也给了你一个额外的页面来打开，但我真的想至少理解一个很好的高层次，这样我就可以自己找到这些算法的复杂性，你的回答非常感谢。

在考试中有人问我，二分搜索是否是一种分而治之的算法。我的回答是肯定的，因为你把问题分成更小的子问题，直到你得到你的结果。

但考官问其中的征服部分在哪里，我无法回答。他们也不赞成它实际上是一种分而治之的算法。

但是我在网上到处都是，它说它是，所以我想知道为什么，它的征服部分在哪里？