问题标签 [divide-and-conquer]

a大小数组中的反转n称为一对(i,j)，它持有i<j和a[i]>a[j]。我正在尝试在 C++ 中实现一个函数，该函数计算给定数组中的反转次数。我遵循分而治之的方法，它只是修改了归并排序算法，并在 O(n log n ) 时间内运行。到目前为止，这是我的代码：

对于某些测试用例，它会产生正确的结果，但对于其他一些测试用例，它会给我错误的输出。我是否错误地理解了算法，或者我在实现时犯了错误？有人可以帮我吗？提前致谢。

O(log N)我想使用分而治之的方法及时找到数组中的最大元素。我在planet-source-code找到了一个工作代码。我将它翻译成 Python 如下：

当我使用数组[98,5,4,3,2,76,78,92]并将代码称为

我收到超出范围的列表索引错误。但是 C 代码返回正确的结果 98。任何人都可以发现我在做什么错误吗？

您有一个大小n为正整数的数组，您最多可以在其上执行以下操作N：

• 选择一个子数组并将其元素值减少k（k必须小于子数组的最小值）。
• 这种操作的代价是子数组的大小乘以k。
• 这些操作的总成本不得大于M。
• NM 可以非常大。

你能给我一个有效的算法来最小化这个数组中的最大元素吗？

我正在尝试实现一个函数，该函数将查看数组的每个元素并确定该特定元素是否大于一个 INT 而小于另一个 INT。例如：

我把它作为一个基本算法，它可以工作，但我想通过使用“分而治之”方法创建一段更有效的代码，但是我在使用递归来使其计数时遇到问题，以及我所拥有的所有示例看到的只是处理一个点的比较，而不是两个。任何人都可以对这种情况有所了解。(http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm)

我的原始代码（线性）：

到目前为止我已经收集到的示例代码（经过数小时的各种工作并使用不同的示例代码后没有运气：

如果这个问题不清楚，对不起，请问您是否需要我详细说明。

分而治之算法和动态规划算法有什么区别？这两个术语有何不同？我不明白它们之间的区别。

请举一个简单的例子来解释两者之间的任何区别以及它们看起来相似的原因。

I recently decided to look at factorial algorithms for large integers, and this "divide and conquer" algorithm is faster than a simple iterative approach and the prime-factoring approach:

I understand why the algorithm works, it just breaks the multiplication into smaller parts recursively. What I don't understand is why this method is faster.

所以我最近对快速计算阶乘产生了兴趣，我写了一个，并从互联网上找了一些其他的来测试。这是代码（Python 2.7）：

我对python并不陌生，我已经将它作为我的主要语言使用了几年，但结果有点出乎意料......

我的问题是，最后一个怎么能快得多？！看看所有的递归！我以为 Python 不喜欢递归！那么为什么速度这么快呢？阶乘2如何工作？另外，大家都知道，我检查了这些都为几个不同的值产生了正确的输出，所以我很确定这些都可以正常工作。

我有一个任务，它比较了一个问题的 2 种不同算法。这是问题所在：

假设我有一系列这样的 xy 坐标：

A(2,3)、B(5,6)、C(7,8)、D(6,2)、E(5,5)等。

我想找到它们之间距离最短的2个坐标。一种解决方案是使用蛮力（一一匹配），但还有另一种使用“分而治之”方法的解决方案。

你能帮我用“分而治之”的方法吗？

当输入字母而不是整数时，我需要输出这些行。我不知道如何让它做到这一点：如果你能帮助我解决这个问题，我有代码和我需要的内容，谢谢。

练习递归和D&C，一个常见的问题似乎是转换数组：我
[a1,a2,a3..an,b1,b2,b3...bn]解决[a1,b1,a2,b2,a3,b3...an,bn]
它如下（startA是asstartB的开始，是s的开始b：

但我不确定运行时是什么。不是线性的吗？