我刚刚完成了一些经典的分治算法的编码，我提出了以下问题：（更多出于好奇）
诚然，在很多情况下，分治算法比传统算法更快；例如，在快速傅里叶变换中，它将复杂度从 N^2 提高到 Nlog2N。但是通过编码，我发现，因为“划分”，我们有更多的子问题，这意味着我们必须创建更多的容器，并在子问题上额外分配更多的内存。想想看，在归并排序中，我们必须在每次递归中创建左右数组，而在快速傅里叶变换中，我们必须在每次递归中创建奇数和偶数数组。这意味着，我们必须在算法期间分配更多的内存。
所以，我的问题是，在现实中，比如在 C++ 中，当我们还必须增加内存分配的复杂性时，像分治法这样的算法真的会赢吗？（或者内存分配根本不需要运行时间，而且成本为零？）
谢谢你的协助！
几乎所有关于优化的事情都是一种资源与另一种资源之间的折衷——在传统工程中，它通常是“成本与材料”。
在计算中，通常是“时间与内存使用”的折衷方案。
我认为您的实际问题没有一个简单的答案-它实际上取决于算法-在现实生活中，这可能会导致妥协的解决方案，将问题分成更小的部分，但并非一直到最小尺寸，只有“直到它不再有效地划分它”。
内存分配不是零成本的操作，如果我们在谈论newand delete。一旦操作系统用物理内存填充了实际的堆栈内存，堆栈内存的成本几乎为零——在大多数体系结构上最多需要一条额外的指令来在堆栈上腾出一些空间，有时在退出时需要一条额外的指令来返还内存.
真正的答案是，几乎总是在性能方面，对不同的解决方案进行基准测试。
了解在大 O 术语中获得“更好的一级”（例如从 n^2 到 n，或从 n 到 log n）通常很重要，这很有用。考虑您的傅立叶示例。
在O(n^2)，n=100你正在看10000，n=1000你得到一百万，1000000。另一方面，O(n*log(n))你得到664forn=100和9965at n=1000。增长放缓应该是显而易见的。
当然，内存分配会消耗资源，分而治之的一些其他代码也是如此，例如组合各个部分。但整个想法是，额外分配等的开销远远小于小型算法所需的额外时间。
额外分配的时间通常不是问题，但内存使用本身可以。这是基本的编程权衡之一。您必须在速度和内存使用量之间做出选择。有时您可以负担额外的内存以获得更快的结果，有时您必须保存所有内存。这是许多问题没有“终极算法”的原因之一。比如说，合并排序很棒，O(n * log(n))即使在最坏的情况下也能运行，但它需要额外的内存。除非您使用就地版本，否则运行速度会变慢。或者，也许您知道您的数据可能已经接近排序，然后像 smoothsort 这样的东西更适合您。