分治算法

陈新龙

今天，我们将学习一种新的Python算法——分而治之。

分治：我们将一个复杂的问题分成两个或更多的相同或类似的子问题，再把子问题分成更小的子问题（分），这些子问题可以简单地直接求解（治），最后将所有子问题的解合并起来就是原问题的解（合）。

分而治之:我们把一个复杂的问题分成两个或两个以上相同或相似的子问题，再把子问题分成更小的子问题(子问题)。这些子问题可以简单的直接解决(解决)。最后，所有子问题的解就是原问题的解(合)。

分治算法适用于数据规模较大的问题。通过分治算法，将数据分解成几个小问题，直到找到正确答案。

例如，我们想要求解列表中的最大值或最小值。为了理解分治算法，我们不使用Python中的max()或min()函数，而是使用分治函数来求解。列表中有很多数据，所以我们会不断缩小要比较的数据。当数据大小为2时，只需要一次判断就可以找到最小值。

求最大值的问题就变成了把几个值分组，直到比较两个数据，用递归从中间分割数据，直到它的小数位数小于等于2，然后比较结果，继续递归比较最后两个数据，求最大值。

在这个程序中对数据使用递归的方法拆分数据，将数据分成两个部分left_list和right_list，当数据的规模等于1的时候可直接判断最值，当数据的规模等于2的时候通过比较可以判断出最值。通过递归与分治的方法便求出列表中的最大值是99了。

在这个程序中，数据用递归的方法分成左链表和右链表两部分。当数据大小等于1时，可以直接判断最大值，当数据大小等于2时，可以通过比较判断最大值。通过递归和分治，列表中的最大值是99。

如果你真的掌握了分而治之的原理，那么你可以尝试做一个题目:“确定一个元素是否在列表中。如果存在，则输出该元素，如果不存在，则显示该数字不存在。”期待你的回答。