官术网_书友最值得收藏!

Algorithm design paradigms

In general, we can discern three broad approaches to algorithm design. They are:

  • Divide and conquer
  • Greedy algorithms
  • Dynamic programming

As the name suggests, the divide and conquer paradigm involves breaking a problem into smaller sub problems, and then in some way combining the results to obtain a global solution. This is a very common and natural problem solving technique, and is, arguably, the most commonly used approach to algorithm design.

Greedy algorithms often involve optimization and combinatorial problems; the classic example is applying it to the traveling salesperson problem, where a greedy approach always chooses the closest destination first. This shortest path strategy involves finding the best solution to a local problem in the hope that this will lead to a global solution.

The dynamic programming approach is useful when our sub problems overlap. This is different from divide and conquer. Rather than break our problem into independent sub problems, with dynamic programming, intermediate results are cached and can be used in subsequent operations. Like divide and conquer it uses recursion; however, dynamic programming allows us to compare results at different stages. This can have a performance advantage over divide and conquer for some problems because it is often quicker to retrieve a previously calculated result from memory rather than having to recalculate it.

主站蜘蛛池模板: 芦溪县| 清水县| 凤山市| 宁国市| 济源市| 张家港市| 龙川县| 杭州市| 深水埗区| 水富县| 健康| 惠水县| 化州市| 七台河市| 通州区| 武平县| 金昌市| 湘阴县| 北票市| 永仁县| 临猗县| 四会市| 会宁县| 手游| 湖口县| 北流市| 察哈| 康马县| 兰溪市| 利川市| 安义县| 岑巩县| 红桥区| 河南省| 盐津县| 蒲江县| 新邵县| 麟游县| 军事| 台安县| 长汀县|