Expert: vijayan - 4/8/2011

Question
how "Divide and Conquer method"  is differ from "Greedy method"?
which One is better?

Answer
> how "Divide and Conquer method"  is differ from "Greedy method"?

A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

For a detailed explanation and several examples, see: http://www.curriki.com/xwiki/bin/view/Coll_nishantgupta/Lesson2DivideandConquerM...



A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding either the global optimum or a solution close to the global optimum.

For an explanation and a simple example, see: http://www.ambesty.com/Content/Tech/GREEDY/default.aspx?sec=2


> which One is better?

Greedy algorithms often do not find the globally optimal solution; because they usually do not operate exhaustively on all the data. They can make commitments to certain choices too early which prevent them from finding the best overall solution later. Nevertheless, Greedy algorithms are very useful to tackle computationally horrendous problems; they are extremely efficient and often results in usable approximations which are fairly close to the optimum.

If a greedy algorithm can be proven to yield the global optimum for a given problem class (examples are Kruskal's algorithm and Prim's algorithm), it typically becomes the method of choice; it then gives the most efficient approach to solving the problem.