Python Data Structure 简明教程

Python - Algorithm Classes

算法是明确的步骤，应该通过处理零个或多个输入向我们提供明确定义的输出。这导致了设计和编写算法的多种方法。已经观察到，大多数算法可以归类为以下类别。

Algorithms are unambiguous steps which should give us a well-defined output by processing zero or more inputs. This leads to many approaches in designing and writing the algorithms. It has been observed that most of the algorithms can be classified into the following categories.

Greedy Algorithms

贪婪算法尝试找到局部最优解，这最终可能会导致全局最优解。但是，贪婪算法通常不提供全局最优解。

Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions. However, generally greedy algorithms do not provide globally optimized solutions.

因此，贪婪算法在此时刻寻找一个简单的解决方案，而无需考虑它如何影响未来的步骤。它类似于人类在不了解所提供输入的完整细节的情况下解决问题的方式。

So greedy algorithms look for a easy solution at that point in time without considering how it impacts the future steps. It is similar to how humans solve problems without going through the complete details of the inputs provided.

大多数联网算法都采用贪婪方法。这里列出一些此类算法−

Most networking algorithms use the greedy approach. Here is a list of few of them −

  1. Travelling Salesman Problem

  2. Prim’s Minimal Spanning Tree Algorithm

  3. Kruskal’s Minimal Spanning Tree Algorithm

  4. Dijkstra’s Minimal Spanning Tree Algorithm

Divide and Conquer

此类算法涉及将给定问题分成较小的子问题，然后独立解决每个子问题。当问题无法进一步子划分时，我们开始合并每个子问题的解，以得出更大问题的解。

This class of algorithms involve dividing the given problem into smaller sub-problems and then solving each of the sub-problem independently. When the problem can not be further sub divided, we start merging the solution to each of the sub-problem to arrive at the solution for the bigger problem.

分而治之算法的重要示例有 −

The important examples of divide and conquer algorithms are −

  1. Merge Sort

  2. Quick Sort

  3. Kruskal’s Minimal Spanning Tree Algorithm

  4. Binary Search

Dynamic Programming

动态规划涉及将较大的问题划分为较小的子问题，但与分而治之不同，它不涉及独立解决每个子问题。相反，它会记住较小子问题的结果，并将其用于相似或重叠的子问题。

Dynamic programming involves dividing the bigger problem into smaller ones but unlike divide and conquer it does not involve solving each sub-problem independently. Rather the results of smaller sub-problems are remembered and used for similar or overlapping sub-problems.

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

Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems.Dynamic algorithms are motivated for an overall optimization of the problem and not the local optimization.

动态规划算法的重要示例有 −

The important examples of Dynamic programming algorithms are −

  1. Fibonacci number series

  2. Knapsack problem

  3. Tower of Hanoi