问题标签 [divide-and-conquer]

我正在阅读有关动态编程的笔记，我遇到了以下评论。

如果子问题不是独立的，即子问题共享子子问题，则分治算法重复解决公共子子问题。因此，它做的工作比必要的多

这是什么意思 ？你能给我举例说明上述观点吗？

当我们谈论分而治之时，我们总是使用递归。我已经知道分而治之是一种算法设计技术，但我有一个问题：

所有分而治之的算法都是递归的，或者换句话说，分而治之的思想在所有的递归中都有使用吗？

我很困惑 。

由于正常分区返回一个索引 j ，使得索引 i <= j 的每个元素都小于选择的枢轴，并且索引 m > j 的每个元素都大于枢轴，因此不能保证 j 是枢轴。是否有可能创建另一个准确返回新枢轴位置的就地分区算法？最初，我坚持将选择的枢轴移动到最后一个位置，但这并没有导致最佳解决方案。

据我了解，Strassen 的矩阵相乘方法应该是最快的……但分治法显然是我测试中最快的……我做错了什么吗？或者这是正确的吗？

指令是：“然后将花费的总时间除以执行算法的次数，以获得解决给定实例所花费的时间”

所以我在每个方法中都有一个单独的“counter++”，并划分时间“recorded / counter++”

到目前为止，这是我的时代：（按自上而下的顺序：经典、分治法、施特拉森）（大小 = 矩阵大小）

尺寸 2

经过时间：8660 纳秒

经过时间：3849 纳秒

经过的时间：5377 纳秒

尺寸 4

已用时间：24864 纳秒

经过时间：3080 纳秒

经过时间：5229 纳秒

8 号

经过时间：125435 纳秒

经过时间：2920 纳秒

经过时间：5196 纳秒

尺寸 16

已用时间：867149 纳秒

已用时间：1559 纳秒

经过时间：2853 纳秒

尺寸 32

已用时间：5191721 纳秒

经过时间：972 纳秒

经过的时间：1722 纳秒

尺寸 64

经过的时间：8155785 纳秒

经过时间：874 纳秒

经过时间：1696 纳秒

样本输出这是我输出的大小为 4 的矩阵的示例：

第一个随机生成矩阵：10 57 33 70
6 12 38 70
20 41 65 98
83 0 31 73
第二个随机生成矩阵：11 70 54 79
2 51 38 71
27 53 37 86
48 87 20 41
经典乘法矩阵：4475 10541
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
经过时间：21232 纳秒

分治乘法矩阵：4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
经过时间：3042 纳秒

Strassen 乘法矩阵：4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
经过时间：5303 纳秒

我被一个问题困住了，我只需要一个大方向的提示/点（不要求答案）

该问题询问分治算法的详细信息，该算法给定几乎已排序的序列，在时间 O(n) 内产生正确的顺序。

他们所说的几乎排序的意思是给定列表

x_1, x_2, .... x_n

如果排序列表由

y_1, y_2, ... y_n

并且对于每一个 i, j <= n 这个属性都受到尊重：

x_i == y_j && |ij| <= 根（n）

我想到的唯一一件事是将列表划分为每个级别的 root(n) 组（这将导致它们在第一次拆分时最多为 root(n)），但我不太确定在哪里从那里开始，因为您必须在递归备份时一次加入 root(n) 元素。

我还发现递归复杂度方程是：

T(n) = root(n) * T(n/root(n)) + d * root(n)

可以master's theorem证明是 O(n) 时间。

所以看起来我在拆分方面走在正确的轨道上，我只是不确定是否应该以特殊方式拆分或比较某种方式或什么。

编辑：所以据说这是正确的答案。

我们的算法如下：如果 n > 1，那么我们递归地对序列的两个（近似）半部分中的每一个进行排序；现在所有元素都在正确的位置，除了中间的√n个位置（你明白为什么这是真的吗？）；所以我们现在对这些位置的元素进行合并。如果我们让 T(n) 是用于对 n 个元素进行排序的时间，那么对于 n > 1，我们有

T(n)≤2T(⌈n=2⌉) +c * √n

由于 √(n) = n ^.5和 .5 < 1 = log ₂ 2，分治循环的主定理告诉我们 T(n)∈O(n)。

我不确定我是否同意，因为对两半进行排序的时间是 O( ⁿ ⁄ ₂ * log( ⁿ ⁄ ₂ ))，结果是 O(n*logn)，最终合并是 O(√ n * √n) 这是 O(n) 给我们总共 O(n*logn + n) -> O(n*logn)

假设维度非常大（矩阵中最多有 10 亿个元素）。我将如何为矩阵向量积实现缓存遗忘算法？根据维基百科，我需要递归地分而治之，但是我觉得会有很多开销..这样做会有效吗？

跟进问答：带矩阵和向量的 OpenMP

我正在尝试使用openmp并行化Guibas Stolfi delaunay 三角测量。

这里有两件事要并行化-我所做的mergesort()和我被卡住的divide() 。我尝试了所有可能的方法，但徒劳无功。

在 divide() 中遵循的方法（除 n 征服）与 mergesort() 相同，但应用相同的并行化技术（omp 部分）仅适用于 mergesort。

我尝试了此处显示的并行化技术，但即使这样也行不通。我在某处读到了嵌套并行性，但我不确定如何实现它。谁能解释分治算法是如何并行化的？

代码：在主函数和应用部分构造中调用了两次合并排序。对除法执行相同操作不起作用

考虑具有以下特殊位置属性的 3SAT 实例。假设布尔公式中有 n 个变量，并且它们的编号为 1,2,3....n，这样每个子句都包含编号在 +-10 范围内的变量。给出求解此类 3SAT 实例的线性时间算法。

我无法解决这个问题，但我的直觉是，如果我们可以将问题映射到图表中，那么可能会得到解决，但不能走得更远..

某个有序类型的元素数组 a[1..n]（即 x < y 总是被定义），我想使用“分而治之”算法找到数组中的最小值。

任务的真正含义是什么？

众所周知，R 并不是运行大型分析的最有效平台。如果我有一个包含三个参数的大型数据框：

我想在每个组上运行一个计算（例如在 X，Y 上计算 Pearson 的 r）并将结果存储在一个新的数据框中，我可以这样做：

明显的问题是这非常慢，即使在强大的多核机器上也是如此。

我的问题是：是否可以并行化这种计算，例如为每个组或一组组设置一个单独的线程？是否有一个干净的 R 模式来解决这个简单的除法问题？

谢谢，穆龙