Python数据结构 算法类

算法是明确的步骤，它应该通过处理零个或多个输入来给我们一个明确的输出。这导致了在设计和编写算法时的许多方法。据观察，大多数的算法可以被分为以下几类。

贪婪算法

贪婪算法试图找到一个局部的最佳解决方案，这可能最终导致全球优化的解决方案。然而，一般来说，贪婪算法并不能提供全局优化的解决方案。

因此，贪婪算法在那个时间点上寻找一个容易的解决方案，而不考虑它对未来步骤的影响。这类似于人类解决问题的方式，没有经过所提供的输入的完整细节。

大多数网络算法都使用贪婪的方法。这里列出了其中的几项–

• 旅行推销员问题

• Prim的最小生成树算法

• Kruskal的最小跨度树算法

• Dijkstra的最小跨度树算法

分而治之

这类算法包括将给定的问题划分为更小的子问题，然后独立解决每个子问题。当问题无法进一步细分时，我们开始合并每个子问题的解决方案，以得出更大问题的解决方案。

分割与征服算法的重要例子有

• 合并排序

• 快速排序

• Kruskal的最小生成树算法

• 二进制搜索

动态编程

动态编程涉及到将大问题分成小问题，但与分而治之不同，它不涉及独立解决每个子问题。相反，较小的子问题的结果被记住并用于类似或重叠的子问题。

大多数情况下，这些算法被用于优化。在解决手头的子问题之前，动态算法会尝试检查以前解决的子问题的结果。动态算法的动机是对问题的整体优化，而不是局部优化。

动态编程算法的重要例子有

• 斐波那契数列

• Knapsack问题

• Hanoi塔