1

I've just finished coding some classical divide-and-conquer algorithms, and I came up the following question:(more for curiosity)

Admittedly, in many cases, divide-and-conquer algorithm is faster than the traditional algorithm; for examples, in Fast Fourier Transform, it improves the complexity from N^2 to Nlog2N. However, through coding, I found out that, because of "dividing", we have more subproblems, which means we have to create more containers and allocate more memories on the subproblem additionally. Just think about this, in merge sort, we have to create left and right array in each recursion, and in Fast Fourier Transform, we have to create odd and even array in each recursion. This means, we have to allocate more memories during the algorithm.

So, my question is, in reality, such as in C++, does algorithms like divide-and-conquer really win, when we also have to increase the complexity in memory allocation? (Or memory allocation won't take run time at all, and it's cost is zero?)

Thanks for helping me out!

4

2 に答える 2

6

最適化に関して言えば、ほぼすべてがリソース対リソース間の妥協です。従来のエンジニアリングでは、通常、「コスト対材料」です。

コンピューティングでは、多くの場合、妥協点は「時間とメモリ使用量」です。

あなたの実際の質問に対する単純な答えは1つではないと思います-それは実際にはアルゴリズムに依存します-そして実際には、これは問題がより小さな部分に分割される妥協の解決策につながる可能性がありますが、すべてが最小サイズ、「分割するのが効率的でなくなるまで」のみ。

newとについて話している場合、メモリ割り当てはゼロコストの操作ではありませんdelete。OS によって実際のスタック メモリに物理メモリが読み込まれると、スタック メモリのコストはほぼゼロになります。ほとんどのアーキテクチャでは、スタックにスペースを確保するための追加の命令が 1 つだけであり、場合によっては終了時に 1 つの追加の命令でメモリを元に戻すことができます。 .

本当の答えは、パフォーマンスに関してはほぼ常にそうであるように、さまざまなソリューションをベンチマークすることです。

于 2013-07-30T13:24:20.857 に答える
5

大きな意味で「1 レベル良くなる」こと (n^2 から n へ、または n から log n への移行など) は、通常、非常に重要であることを理解しておくと便利です。フーリエの例を考えてみましょう。

でO(n^2)、n=100あなたが見ている で10000、あなたはn=1000100 万を取得します1000000。一方、 with ではforとatO(n*log(n))が得られます。ゆっくりとした成長は明らかです。664n=1009965n=1000

もちろん、メモリの割り当てにはリソースが必要です。パーツの結合など、分割統治に必要な他のコードも同様です。しかし、全体的な考え方は、余分な割り当てなどによるオーバーヘッドは、小さなアルゴリズムに必要な余分な時間よりもはるかに小さいということです。

通常、余分な割り当ての時間は問題になりませんが、メモリの使用自体は問題になる可能性があります。これは、基本的なプログラミングのトレードオフの 1 つです。速度とメモリ使用量のどちらかを選択する必要があります。より高速な結果を得るためにメモリを追加できる場合もあれば、すべてのメモリを節約しなければならない場合もあります。これが、多くの問題に対して「究極のアルゴリズム」が存在しない理由の 1 つです。たとえば、mergesort はO(n * log(n))最悪のシナリオでも実行できる優れた機能ですが、追加のメモリが必要です。インプレース バージョンを使用しない限り、実行速度が遅くなります。または、データがすでにニアソートされている可能性が高いことを知っている場合は、smoothsort のようなものが適しているかもしれません。

于 2013-07-30T13:28:25.183 に答える