c++ - 分而治之真的能战胜增加的内存分配吗？

Question

我刚刚完成了一些经典的分而治之算法的编码，我想到了以下问题:(更多出于好奇)

不可否认，在很多情况下，分而治之算法比传统算法更快；例如，在 Fast Fourier Transform 中，它将复杂度从 N^2 提高到 Nlog2N。但是，通过编码，我发现，由于“划分”，我们有更多的子问题，这意味着我们必须额外创建更多的容器并为子问题分配更多的内存。试想一下，在归并排序中，我们必须在每次递归中创建左右数组，而在快速傅立叶变换中，我们必须在每次递归中创建奇数和偶数数组。这意味着，我们必须在算法期间分配更多内存。

所以，我的问题是，在现实中，例如在 C++ 中，当我们还必须增加内存分配的复杂性时，像分而治之这样的算法真的会赢吗？ (或者内存分配根本不需要运行时间，成本为零？)

谢谢你帮助我!

Answer 1

几乎所有涉及优化的事情都是一种资源与另一种资源之间的折衷——在传统工程中，这通常是“成本与 Material ”。

在计算中，折衷通常是“时间与内存使用”。

我认为您的实际问题没有一个简单的答案 - 它实际上取决于算法 - 在现实生活中，这可能会导致折衷的解决方案，将问题分成更小的部分，但不是全部缩小到最小尺寸，只是“直到它不再有效地划分它”。

内存分配不是零成本操作，如果我们谈论new 和delete。一旦操作系统用物理内存填充了实际的堆栈内存，堆栈内存的成本几乎为零——在大多数体系结构上，它最多是一条额外的指令来在堆栈上腾出一些空间，有时在退出时需要一条额外的指令来归还内存.

真正的答案是，几乎总是在性能方面，对不同的解决方案进行基准测试。