Home » 文档 » 分治的思想解决问题

分治的思想解决问题

当我们遇到难题时,不妨想一想分治思想。分治就是分而治之。将原问题划分成多个规模较小,并且与原问题相似的子问题,子问题还可以再进行分解成子问题,分解到子问题可以直接求解时,再逐步向上归并,最终得到原问题的解。
最经典的运用分治思想的就是归并排序算法,也是时间复杂度较低「O(nlogn)」的算法中最容易实现的。

如何求解序列的有序度?

学习算法最好的方式是编码来解决一个问题,这里给出一个问题:如何高效地求解一组数据的有序度?
有序度代表一组数据有序的程度,就是序列中有序对的个数,相对应的为逆序度。
  • 比如 1,2,3 这组数据完全有序,(1,2),(1,3),(2,3)都是有序的,因此有序度为 3,逆序度为 0 。
  • 比如 1,3,2 这组数据不完全有序,(1,3),(1,2)都是有序的,(3,2)是逆序的,因此有序度为 2,逆序度为 1 。
  • 比如 3,2,1 这组数据完全无序,(3,1),(3,2),(2,1)是逆序的,因此有序度为 0,逆序度为 3 。
比如,输入 2,4,3,1,5,6,输出的有序度为 11。
最简单的方法就是循环,每次循环都在剩余元素中找比当前元素大的数据,记为 k,最后对 k 求和,不过这样做的时间复杂度是 O(N^2),在数据量不大的情况下,使用简单的算法往往比较好用。简单意味着不易出错。当数据量大时,就要追求更快的方法。
求解一组数据的有序度,其实还可以采用分治的思想,时间复杂度为 O(nlogn)。
思路如下:数组 A 直接求不容易,那就对它进行分解成 B 和 C,如果 B 的有序度为 k1,C 的有序度为 k2,B 和 C 之间的有序度为 k3,那么数组 A 的有序度就是 k1 + k2 + k3。
如果元素较多,仍然可继续分解。直到 B 和 C 分别只有一个元素,比如 B 是 [2] ,C 是 [4] ,此时 B 和 C 自身不存在有序度,由于 B 中的元素比 C[0] 小的个数是 1 ,因此 B 和 C 之间的有序度是 1,即 k1 = 0,k2 = 0,k3 = 1。
继续归并,B=[2,4] C=[3,1] ,此时可求得 k1 = 1,k2 = 0,k3 = 1,k3 就代表 B 中元素小于 C 中元素的个数的和。
继续归并,此时特别近似于归并排序算法,对 B 和 C 分别排序后可以更快的求出 k3,这里我们已经了解到排序的本质:排序是增加有序度,降低逆序度的过程。求解有序度和逆序度,对于选择排序算法很有帮助。
如果你觉得上述文字描述不太容易理解,那么从代码中理解也是一种很好的方式,下面自己实现求有序度、逆序度,并打印出有序对和逆序对的代码。
# -*- coding: utf-8 -*-
# !/usr/local/bin/python
# Time: 10/31/2019 9:44:19 PM
# Description:
# File Name: get_degree_of_order.py

yxd, nxd = 0, 0
yxd_pair ,nxd_pair = [],[]

def get_yxd_nxd(array):
global yxd,nxd
yxd, nxd = 0, 0
mergSortCounting(array[:] ,0,len(array)-1)
print(f”原始数组{array} \n有序度为{yxd} : {yxd_pair}\n逆序度为{nxd} : {nxd_pair}”)
return yxd,nxd

def mergSortCounting(array,low,high):
if low >= high:
return
middle = (low + high)//2
mergSortCounting(array,low,middle)
mergSortCounting(array,middle+1,high)
merge(array,low,middle,high)

def merge(array,low,middle,high):
global yxd,nxd,yxd_pair,nxd_pair
array1 = array[low:middle+1]
len_array1 = len(array1)
array2 = array[middle+1:high+1]
len_array2 = len(array2)
i,i1,i2 = low,0,0

while i1 < len_array1 and i2 < len_array2:
if array1[i1]  <= array2[i2] :
array[i]  = array1[i1]

#在array2中找到比array1[i1] 大的数据个数,并累加
yxd += len_array2 – i2

##增加对有序对的记录,方便理解。
for x in range(i2,len_array2):
yxd_pair.append((array1[i1] ,array2[x] ))

i += 1
i1 += 1

else:
array[i]  = array2[i2]

#在array1中找到比 array2[i2]  大的个数,并累加
nxd += len_array1 – i1

##增加对逆序对的记录,方便理解。
for x in range(i1,len_array1):
nxd_pair.append((array1[x] ,array2[i2] ))

i += 1
i2 += 1

while i1 < len_array1:
array[i]  = array1[i1]
i += 1
i1 += 1

while i2 < len_array2:
array[i]  = array2[i2]
i += 1
i2 += 1

if __name__ == “__main__”:
array_list = [2,4,3,1,5,6]
get_yxd_nxd(array_list)

执行结果如下:
原始数组[2, 4, 3, 1, 5, 6]
有序度为11 : [(2, 4), (2, 3), (1, 5), (1, 6), (5, 6), (2, 5), (2, 6), (3, 5), (3, 6), (4, 5), (4, 6)]
逆序度为4 : [(4, 3), (2, 1), (3, 1), (4, 1)]
关于分治算法还有不少可以练手的题目,比如找出二维平面上 n 个点中距离最近的两个点。

分治算法思想的在技术上的应用

1、MapReduce
MapReduce 实际上是一种编程模型,主要是用于处理大规模数据集,其实现核心逻辑实际上是跟分治方法是统一的。在这个编程模型下,用户只需要关心两个函数,一个是 map 函数,用于处理一个键值对,然后生成一个中间键值对的数据集合。另一个是 reduce 函数,是用来将 map 产生的中间键值对数据集根据相同中间键来进行合并操作。这种编程模型自然而然的是可以通过在一个集群上进行并行的处理。整个系统需要做的是划分输入数据、调度作业任务与机器、处理机器故障以及管理机器间的通信等等,
map(String key, String value):
//key: document name
//string: document contents
for each word w in value :
EmitIntermediate(w, “1”);

reduce(String key, Iterator values):
//key : a word
//values : a list of counts
for each v in values:
result += ParseInt(v);
Emit(AsString(result));

这个 map 函数会将每个 word 都填上一个 1 的词频数发射出去,然后 reduce 函数将同一个 word 发射出来的数目加起来。分治的思想就是这么简单有效。
大部分编程语言也提供了类似的 map 和 reduce 函数,强烈推荐这类高阶函数,因为它们的效率非常高,比如 Python 中的函数使用方法如下:
>>> from functools import reduce
>>> def pow(x):
…     return x*x

>>> def add(x,y):
…     return x+y

>>>
>>> data = [1,4,7]
>>>
>>> list(map(pow,data))
[1, 16, 49]
>>> reduce(add,data)
12
2、处理海量数据。
假如内存只有 4GB ,如何给 10GB 的订单排序呢?我们可以先逐行扫描一遍订单,根据订单金额将 10GB 文件划分多个金额区间,比如将 1 – 100 元的放在文件 1 , 100 – 200 元的放在文件 2 ,依次类推,每个小文件都可以单独加载到内存中排序,最后将这些小文件合并,就是有序的 10GB 订单数据了。
3、归并排序、桶排序、快速排序也都使用了分治算法的思想。
4、复杂的工程项目分多个文件,多个模块,也是一种分治思想。

分治算法思想的在生活中的应用

1、人口普查。
2、小到公司管理、大到国家管理。
3、美国大选。
4、团队目标实现。leader:设置一个团队的整体目标, module owner:分取整体目标的一个模块。developer:分取模块里面一个任务。整体目标 = 模块任务 A + 模块任务 B ,模块任务 A  = 个人任务 A  + 个人任务 B  + 个人任务 C ,最后达到整个任务。

算法的魅力

借用王争老师的话做为结尾:创新并非离我们很远,创新的源泉来自对事物本质的认识。无数优秀架构设计的思想来源都是基础的数据结构和算法,这本身就是算法的一个魅力所在。