我们如何对各种算法进行分类？
我听过各种名称:分而治之算法、确定性算法、概率算法、就地算法等。
它们是否形成任何类型的分类层次结构？
请提供任何网络链接。
最佳答案
算法有一些不同的分类:
他们解决问题的方式
经典算法:
- Divide & Conquer像二进制搜索
- Greedy Algorithms比如在列表中找到最大值，或者使用未加权的工作值找到最大的工作分配。
- Dynamic Programming , 像 LCS
- Backtracking ，像 8 queen，和所有的 NPC 算法。
- Sorting Algorithms , 排序有特定的方法论和广泛的应用
- Linear Programming
- Graph Algorithms
非经典的:
但是这种算法是确定性的或非确定性的，意味着每次在特定输入上运行它们将得到相同的结果(确定性的)或不同的结果(非确定性的)。
而且这个算法有太多不同的问题，每个问题都使用所有算法的混合，例如欧几里德图中的TSP可以通过使用dfs和图算法来近似，随机游走，....和ATSP (非对称图中的 TSP)可以通过线性规划和一些高级图算法的组合来近似。
但是有一个著名的问题分类，我们可以将其扩展到时间复杂度的算法(还有内存，但现在内存不再像时间那样受到关注):
- P
- NP
- 全国人大
- NPC强
- NP 困难
- 共同NP
- ...
关于algorithm - 我们如何对各种算法进行分类？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4420671/