Can*_*can 0 c++ algorithm memory-management divide-and-conquer
我刚刚编写了一些经典的分治算法,我提出了以下问题:(更多是好奇心)
不可否认,在许多情况下,分而治之算法比传统算法更快; 例如,在快速傅里叶变换中,它提高了从N ^ 2到Nlog2N的复杂度.然而,通过编码,我发现,由于"划分",我们有更多的子问题,这意味着我们必须创建更多的容器并在子问题上分配更多的记忆.考虑一下,在合并排序中,我们必须在每次递归中创建左右数组,而在快速傅里叶变换中,我们必须在每次递归中创建奇数和偶数数组.这意味着,我们必须在算法期间分配更多的内存.
所以,我的问题是,实际上,比如在C++中,当我们还必须增加内存分配的复杂性时,像分而治之类的算法真的会赢吗？(或者内存分配根本不需要运行时间,而且成本是零？)
谢谢你的协助!
在优化方面,几乎所有事情都是在一种资源与另一种资源之间的折衷 - 在传统工程中,它通常是"成本与材料".
在计算中,通常"时间与内存使用"是妥协.
我不认为对你的实际问题有一个简单的答案 - 它实际上取决于算法 - 在现实生活中,这可能导致妥协解决方案,其中问题被分成更小的部分,但不是一直到最小尺寸,只有"直到它不再有效地划分它".
如果我们谈论new和,内存分配不是零成本操作delete.一旦实际的堆栈内存被操作系统填充了物理内存,堆栈内存几乎为零成本 - 在大多数架构上最多只有一条额外的指令可以在堆栈上占用一些空间,有时在退出时会有一条额外的指令将内存返回.
真正的答案是,几乎总是在性能方面,对不同的解决方案进行基准测试.
理解在大O项中获得"一级更好"(例如从n ^ 2到n,或从n到log n)通常很重要.考虑你的傅里叶例子.
在O(n^2),有n=100你正在寻找10000,并与n=1000你的整体万元,1000000.在另一方面,O(n*log(n))你得到664的n=100与9965在n=1000.增长放缓应该是显而易见的.
当然,内存分配会花费资源,分而治之需要的其他一些代码也是如此,例如组合部分.但是整个想法是额外分配的开销远远小于小算法所需的额外时间.
额外分配的时间通常不是问题,但内存使用本身也可以.这是基本的编程权衡之一.您必须在速度和内存使用之间进行选择.有时您可以负担得起额外的内存以获得更快的结果,有时您必须保存所有内存.这就是为什么没有针对许多问题的"终极算法"的原因之一.说,mergesort很棒,O(n * log(n))即使在最糟糕的情况下运行,但它需要额外的内存.除非您使用就地版本,然后运行速度较慢.或许你知道你的数据可能已经接近排序,然后像smoothsort这样的东西更适合你.