法→原理, 算法实现

经典算法之分治法

钱魏Way · · 206 次浏览

分治法概念

分治法(divide-and-conquer)字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。分治有两个特点:

  1. 子问题相互独立且与原问题形式相同
  2. 反复分治,使划分得到的子问题小到不能再分时,直接对其求解

分治法所能解决的问题一般具有以下特征:

  1. 该问题的规模缩小到一定程度就可以容易的解决。
  2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构的性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解(关键性质)
  4. 该问题所分解出的各个子问题最好是相互独立的,即子问题之间不包含公共的子问题。

其中:

  • 第一条特征是绝大多数问题都能满足的,因为计算复杂性一般随着规模的减小而降低。
  • 第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用。
  • 第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征。如果具备了第一条特征和第二条特征,而子问题的解不可以合并,则可以考虑贪心算法或动态规划。
  • 第四条特征涉及分治法的效率,如果各子问题不是独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

分治模式在每一层递归上都有三个步骤:

  • 分解(Divide):将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
  • 解决(Conquer):若子问题规模较小而容易求解则直接求解,否则递归的解决各个子问题。
  • 合并(Combine):将各个子问题的解合并为原问题的解。

分治法的一般算法框架如下:

divide_and_conquer(problem)
{
    if(|problem| < n) adhoc(problem);            /*解决小规模的问题*/
    divide Problem into smaller subinstances P1,P2,....Pk;/*分解问题*/
    for(i = 1; i<= k(子问题个数); ++i){
        result[i] = divide_and_conquer(P[i]);   /*递归的解各个子问题*/
    }
    return merge(result[1]...result[k]);    /*将各个子问题的解合并为原问题的解*/
}

分治法求解的一些经典问题:

  • 二分搜索
  • 大整数乘法
  • Strassen矩阵乘法
  • 棋盘覆盖
  • 合并排序
  • 快速排序
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表
  • 汉诺塔

分治法的典型实例

二分搜索

问题描述:给定已按照升序排列好的n个元素 a[0:n-1],现在要在这n个元素中找出一特定元素。

问题分析:采用分治法的思想,充分利用元素之间已经存在的次序关系,将序列划分为两个个数相同的左右两个部分,取最中间的元素和x进行比较,如果等于中间的元素就找到,如果不等于,就递归的在左边(x<中间值)或者右边(x>中间值)二分查找。

注意事项:对于二分查找,一般需要建立两个不变性:

  • 当前待查找序列,肯定包含目标元素
  • 每次待查找序列的规模都会变小。

Python示例:

# -*- coding: utf-8 -*-

def binary_search(array, t):
    low = 0
    height = len(array) - 1
    while low < height:
        mid = low + (height - low) // 2
        # 用 mid = (begin+end) // 2 是有溢出危险的,对于一个规模足够大的数组(极端假设为2147483647个元素),那么在对后半部(2/n~n)取mid时,使用mid = (end + start) / 2溢出(结果会得到一个负数)
        if array[mid] < t:
            low = mid + 1
        elif array[mid] > t:
            height = mid - 1
        else:
            return array[mid]
    return -1

if __name__ == "__main__":
    print(binary_search([1, 2, 3, 34, 56, 57, 78, 87], 57))

快速排序

快速排序(Quicksort),是一种排序算法,最坏情况复杂度:Ο(n2),最优时间复杂度:Ο(n log n),平均时间复杂度:Ο(n log n)。快速排序的基本思想也是用了分治法的思想:找出一个元素X,在一趟排序中,使X左边的数都比X小,X右边的数都比X要大。然后再分别对X左边的数组和X右边的数组进行排序,直到数组不能分割为止。

快速排序的基本思想:设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

  • 分解:在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。(注意:划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]):R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys,其中low≤pivotpos≤high。)
  • 求解:通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
  • 组合:因为当”求解”步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,”组合”步骤无须做什么,可看作是空操作。

Python实现:

# -*- coding: utf-8 -*-

# 方法1
def quickSort(arr):
    less = []
    pivotList = []
    more = []
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]  # 将第一个值做为基准
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)

        less = quickSort(less)  # 得到第一轮分组之后,继续将分组进行下去。
        more = quickSort(more)

        return less + pivotList + more


# 方法2
# 分为<, >, = 三种情况,如果分为两种情况的话函数调用次数会增加许多,以后几个好像都有相似的问题
# 如果测试1000个100以内的整数,如果分为<, >=两种情况共调用函数1801次,分为<, >, = 三种情况,共调用函数201次
def qsort(L):
    return (
        qsort([y for y in L[1:] if y < L[0]])
        + L[:1] + [y for y in L[1:] if y == L[0]]
        + qsort([y for y in L[1:] if y > L[0]])
    ) if len(L) > 1 else L


# 方法3
# 基本思想同上,只是写法上又有所变化
# def qsort(list):
# if not list:
# return []
#     else:
#         pivot = list[0]
#         less = [x for x in list if x < pivot]
#         more = [x for x in list[1:] if x >= pivot]
#         return qsort(less) + [pivot] + qsort(more)


#方法4
from random import *


def qSort(a):
    if len(a) <= 1:
        return a
    else:
        q = choice(a)  #基准的选择不同于前,是从数组中任意选择一个值做为基准
        return qSort([elem for elem in a if elem < q]) + [q] * a.count(q) + qSort([elem for elem in a if elem > q])


#方法5
#这个最狠了,一句话搞定快速排序,瞠目结舌吧。
qs = lambda xs: \
    ((len(xs) <= 1 and [xs]) or [
        qs([x for x in xs[1:] if x < xs[0]]) + [xs[0]] + qs([x for x in xs[1:] if x >= xs[0]])] )[
        0]

if __name__ == "__main__":
    a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
    print(quickSort(a))
    print(qsort(a))
    print(qSort(a))
    print(qs(a))

发表评论

邮箱地址不会被公开。 必填项已用*标注