问题标签 [divide-and-conquer]

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

请注意，此 mergeSort 函数不起作用，因为我还没有弄清楚如何合并它们（这是我的任务）。我想在处理它之前对我的两个向量进行排序，但我无法编译它，因为我需要将数组作为参数传递。我不明白指针，所以如果这是解决方案，我的借口是无知。我现在正在学习编程，以 C++ 作为第一语言，并且只对语言的特性有一个基本的掌握。谢谢您的帮助。

我们如何从值创建节点集....

我有 n 个数字 1,2,3.......n。

我想创建一个节点集

我想知道分而治之的技术是否总是将一个问题分成相同类型的子问题？通过相同的类型，我的意思是可以使用具有递归的函数来实现它。分治法总是可以通过递归来实现吗？

谢谢！

我们有两个大小为 n 的数据库，其中包含没有重复的数字。所以，我们总共有 2n 个元素。它们可以通过一次查询一个数据库来访问。查询是这样的，您给它 ak 并返回该数据库中的第 k 个最小条目。我们需要在 O(log n) 查询的所有 2n 个元素中找到第 n 个最小的条目。

这个想法是使用分而治之，但我需要一些帮助来思考这个问题。谢谢！

我搜索了一些教程，浏览了一些 SO 答案，但无法找到解决我问题的方法。

我正在编写一个应该显示几乎实时股票图表的网站。数据存储在不断更新的 MySQL 数据库中，我编写了一个 find_by_sql 查询代码，它获取绘制图表所需的所有数据。一切都很好，除了性能 - 不同查询从数据库中获取所有数据需要一秒到一分钟，这次包括必要的（My）SQL 服务器端计算。这简直不能接受。

我得到了以下想法：如果一次从 MySQL 服务器查询数据而不是整个数据集，则只需大约 1-100ms 即可获得单个点。

我想数据获取过程可能是浏览器驱动的。在用户按下按钮以绘制图表后，控制器向数据库发出一个请求，并呈现一个进度条，比如说准备好 1%。当浏览器得到响应时，它立即发出（ajax）请求，服务器获取下一条数据并呈现“2%”。

以此类推，直到所有数据都准备好并且服务器显示请求的图表。这可以在rails+js中实现吗，网上有解决类似问题的教程吗？我想如果这件事完全可行，那么之前应该已经有人这样做了。

我已经阅读了几篇关于 ajax 的文章，我相信我确实了解一般原则，但我自己从未做过非平凡的 ajax 编程。

谢谢你的时间！

更新：我为这个问题添加了一个答案，其中包含了几乎所有已给出的建议。下面代码中给出的原始模板需要45605 毫秒才能完成一个真实世界的输入文档（关于脚本编程的英文文本）。社区 wiki 答案中修改后的模板将运行时间降至 605 毫秒！

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

这个模板占了我的 XSLT 脚本所需的大部分运行时间。将上面的escape-text模板替换为just

使我的 XSLT 脚本的运行时间在我的一个文档上从 45 秒缩短到不到 1 秒。

因此我的问题是：我怎样才能加快我的escape-text模板？我正在使用xsltproc，我更喜欢纯 XSLT 1.0 解决方案。XSLT 2.0 解决方案也将受到欢迎。但是，外部库可能对这个项目没有用——尽管我仍然对使用它们的任何解决方案感兴趣。

可能重复：
在数字数组中查找缺失数字的最快方法

输入：未排序的数组 A[1,..,n] 包含范围 0,..,n 中除一个整数之外的所有整数

问题是在 O(n) 时间内确定丢失的整数。A 的每个元素都用二进制表示，唯一可用的操作是函数 bit(i, j)，它返回 A[i] 的第 j 位的值，并花费常数时间。

有任何想法吗？我认为某种分而治之的算法是合适的，但我想不出我到底应该做什么。提前致谢！

如果使用分而治之算法，我如何能够找到数组中至少一半的对象是否返回 true（在某些函数上）？对象没有可枚举的值，因此对象 A 绝不大于对象 B。

为了澄清，使用该功能将所有对象相互比较。所以 funct(Obj a, Obj b) 根据某些标准返回真或假。它们可以聚集在一起，我们只想知道是否至少有一半的比较对象返回 true。

自从我一直在研究这个问题以来，这个问题一直困扰着我。我试图找出一种方法来确定某些人是否根据他们的配对生活在一起。例如，我得到一个列表：

我需要一个 D&C 算法来比较这个列表的所有元素，看看是否至少有一半是生活在一起的。为了确定他们是否住在一起，给出了一个简单的函数：如果他们住在一起，则LivesTogether(x, y)返回 true，否则返回 false。

有任何想法吗？

这是一道作业题，已经介绍过二分查找：

给定两个数组，分别按升序排列的N和M个元素，不一定唯一：在两个数组的联合中
找到第k个最小元素的高效算法是什么？

他们说它需要O(logN + logM)数组长度N和位置。M

让我们命名数组a和b. 显然我们可以忽略所有a[i]以及b[i]i > k 的地方。
首先让我们比较a[k/2]和b[k/2]。让b[k/2]> a[k/2]。因此，我们也可以丢弃所有b[i]，其中 i > k/2。

现在我们有了 all a[i], where i < k 和 all b[i], where i < k/2 来找到答案。

你下一步怎么做？