問題タブ [divide-and-conquer]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 配列内のピークを見つける際に適用される分割統治アルゴリズム。
配列 a: a 1 , a 2 , … a k , … a nの場合、 1 < k および k < n のときにa k-1 ≤ a k ≥ a k+1である場合に限り、a kはピークです。a 1 ≥ a 2の場合、a 1はピークであり、a n-1 ≤ a nの場合、 a nはピークです。目標は、配列から 1 つのピークを見つけることです。
分割統治アルゴリズムは次のように与えられます。
このアルゴリズムが正しいのはなぜですか? ピークが存在するアレイの半分を失うことで問題が発生する可能性があると思います。
c++ - Does divide-and-conquer really win against the increased memory allocation?
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!
c++ - クイックソートの実装エラー
クイックソートを実装しようとしていました。しかし、コントロールはクイックソート機能を終了していないようです。どんな助けでも大歓迎です。
いくつかの指針：
- 最初の要素をピボットとして使用しています。ピボットを選択するためのより優れた効率的な手法が存在することは知っていますが、これはそれだけではありません。
2.パーティション関数の「k」変数はピボット要素です。
私が知る限り、問題はパーティション機能にあります。これは、何度もデバッグを試みたためです。
また、これは宿題の質問ではありません。独学で学んだアルゴリズムを実装しようとしていました。
main 関数では、quicksort(0,n,a) と quicksort(0,n-1,a) の両方を使用してみました。どちらも機能しませんでした。
c++ - SPOJ Feynman で動的計画法を適用するには?
私はこの問題を解決していました-> http://www.spoj.com/problems/SAMER08F/ (非常に単純な問題) ... 最初に AC を取得しました... 私の解決策は次のようなものでした (かなり単純明快です) :
私はこのリストhttp://ahmed-aly.com/Category.jsp?ID=33を調べていて、ファインマンがDPの問題としてリストされているのを見つけました...私はDPの初心者で、この問題がどのように構成されているのかわかりませんサブ問題の。再帰関係を見つけるためのヘルプやヒントは非常に役立ちます。
algorithm - 分割して征服する と 減算して征服する の違いは?
再帰について読んで、再帰方程式を解いています。「減算して征服する」という用語に出くわしました。「分割統治法」との違いは? 分割統治法 (マスター定理や再帰ツリーなど) の再帰方程式を解くために使用されるのと同じ手法を使用して、この種の問題を解決できますか?