- Python Data Structures and Algorithms
- Benjamin Baka
- 218字
- 2021-07-09 19:45:06
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.
- Web應(yīng)用系統(tǒng)開發(fā)實踐(C#)
- Java完全自學(xué)教程
- Practical Internet of Things Security
- Django Design Patterns and Best Practices
- SQL經(jīng)典實例(第2版)
- Web Development with MongoDB and Node(Third Edition)
- Visual FoxPro程序設(shè)計習(xí)題集及實驗指導(dǎo)(第四版)
- Microsoft Azure Storage Essentials
- Linux Shell核心編程指南
- Scratch3.0趣味編程動手玩:比賽訓(xùn)練營
- Python 3快速入門與實戰(zhàn)
- jQuery Mobile Web Development Essentials(Second Edition)
- C# 10核心技術(shù)指南
- Visual FoxPro數(shù)據(jù)庫程序設(shè)計
- Unreal Engine 4 Game Development Essentials