美文网首页
算法思想 - 分治算法

算法思想 - 分治算法

作者: 天命_风流 | 来源:发表于2020-04-07 13:13 被阅读0次

其实相比于分治算法,我更愿意称之为分治“思想”。因为这种思想的应用非常广泛,不仅是在计算机中,在生活中到处都是分治思想的影子。当一项工程庞大到一个个体无法完成,我们就需要和别人进行合作,这种合作其实就是分治思想。当然,具体到计算机领域,分治算法就有了更加严格的约束。

分治算法

分治算法(divide and conquer)的核心思想就是四个字,分而治之。也就是将问题划分成多个规模较小,并且结构与元问题相似的子问题,依次(常常使用递归)地解决这些子问题,然后再合并其结果,就可以得到原问题的解。

分治算法的基础步骤

由于分治算法常常使用递归来实现,所以推广开来,在使用递归实现分治算法的过程中,每一层递归都应该有这样三个操作:

  • 分解:将原问题分解成一系列子问题
  • 解决:当问题分解到一定程度,可以很容易地解决这个问题
  • 合并:将子问题的结果合并,最终形成原问题的解

分治算法要满足的条件

一个算法是直接运行在计算机上的,所以一个算法首先要能够在计算机上实现,因此,我们会对分治算法提出一些要求:

  • 原问题和分解后的小问题具有相同的模式。如果你的问题非常复杂,分解后需要解决的问题很多,那你应该考虑将这个问题定义为一项“工程”,而不要尝试使用一个算法就解决它
  • 元问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法和动态规划的最明显的区别。
  • 具有分解终止条件。当问题足够小时,可以直接求解,这也对应了递归中的终止条件。
  • 可以将子问题的结果合并成原问题的结果,且合并不能太复杂

分治算法应用举例

分治算法的原理非常简单,但是想要灵活应用却很不容易。接下来,让我们通过一个例子,深入了解分治算法的思想。

在之前的排序算法中,我们讲过有序度和逆序度的概念,它等于一个数组中逆序对的个数: 逆序对.jpg

请问,如何求一组数的逆序度呢?

最先想到的就是对每个数组逐一和后面的数字进行比对,将逆序度相加,这是非常暴力的解决方式,我们可以使用分治算法来试试:

我们想求数组 A 的逆序对的个数,首先可以将它分解成前后两半 A1 和 A2 ,分别计算他们的逆序对个数 K1 和 K2,然后计算 A1 与 A2 之间的逆序对个数 K3。则数组A 的逆序对个数就是 K1+K2+K3。

这个过程是不是让你想到了归并排序?没错,我们可以通过改造归并排序,得到一个数组的逆序度。

归并排序中有一个非常关键的操作,就是合并两个数组,在这个合并的过程中,我们可以计算两个数组的逆序对个数了。每次合并操作,我们都可以计算一部分逆序度,当合并完成时,就可以获得这个数组的逆序数了:


求逆序对-使用归并.jpg

具体代码如下:

private int num = 0; // 全局变量或者成员变量

public int count(int[] a, int n) {
  num = 0;
  mergeSortCounting(a, 0, n-1);
  return num;
}

private void mergeSortCounting(int[] a, int p, int r) {
  if (p >= r) return;
  int q = (p+r)/2;
  mergeSortCounting(a, p, q);
  mergeSortCounting(a, q+1, r);
  merge(a, p, q, r);
}

private void merge(int[] a, int p, int q, int r) {
  int i = p, j = q+1, k = 0;
  int[] tmp = new int[r-p+1];
  while (i<=q && j<=r) {
    if (a[i] <= a[j]) {
      tmp[k++] = a[i++];
    } else {
      num += (q-i+1); // 统计p-q之间,比a[j]大的元素个数
      tmp[k++] = a[j++];
    }
  }
  while (i <= q) { // 处理剩下的
    tmp[k++] = a[i++];
  }
  while (j <= r) { // 处理剩下的
    tmp[k++] = a[j++];
  }
  for (i = 0; i <= r-p; ++i) { // 从tmp拷贝回a
    a[p+i] = tmp[i];
  }
}

如果你是python使用者,你可以参考我的代码(我直接使用了之前在归并排序中给出的代码,所以都是之前的注释)

import random

l = [40, 55, 94, 82, 60, 20, 42, 70, 93, 58]
a = [20, 40, 42, 55, 58, 60, 70, 82, 93, 94]

num = 0  # 设置一个全局变量

def merge_sort(L):
    '''
    启动归并排序
    :param L: 待排序数组
    :return: 无返回
    '''
    _merge_sort(L, 0, len(L) - 1)


def _merge_sort(L, left, right):
    '''
    在这个函数中实现递归
    :param L:
    :param left: 归并区间的起始指针(角标)
    :param right: 结束指针(角标)
    :return: 无返回
    '''
    if left < right:
        mid = (left + right) // 2
        _merge_sort(L, left, mid)
        _merge_sort(L, mid + 1, right)
        merge(L, left, mid, right)
        # 请注意调用顺序,我们先分割排序,然后合并


def merge(L, left, mid, right):
    '''
    合并两个数组,这里需要使用一个临时数组存储合并的数据
    '''
    global num  # 声明num为全局变量
    temp = []
    i = left  # i为左边数组的起始位置
    j = mid + 1  # j为右边数组的起始位置
    while i <= mid and j <= right:  # 两边数组进行比较
        if L[i] < L[j]:
            temp.append(L[i])
            i += 1
        else:
            num += mid - i + 1  # 计算逆序度
            temp.append(L[j])
            j += 1

    # 确保两个指针都走到最后
    while i <= mid:
        temp.append(L[i])
        i += 1

    while j <= right:
        temp.append(L[j])
        j += 1

    L[left:right + 1] = temp  # 将临时变量放入数组中


# _sort = merge_sort(l)
# print(_sort)
# print(l)

if __name__ == "__main__":
    data = list(range(5))
    random.shuffle(data)
    print(data)
    merge_sort(data)
    print(data)
    print(num)

总结

分治算法的思想在于:拆->解决->合并。这是一个非常重要的算法思想,实际上,之前我们讲到的很多内容都用到了分治的思想,在这里,就不过多介绍相关例子了,你可以回顾之前的内容,相信你会有更多收获。
以这个思想为基础,人们建立了计算机中的分布式集群处理系统。两者的差距似乎很大,但是它们的联系却又如此简单。最后,附上专栏老师的一段话,希望你可以走的更远:

其实,创新并非离我们很远,创新的源泉来自对事物本质的认识。无数优秀架构设计的思想来源都是基础的数据结构和算法,这就是算法的魅力所在。


以上就是分治算法的全部内容

注:本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结,我使用了大量的原文、代码和截图,如果想要了解具体内容,可以前往极客时间

相关文章

  • 分治算法

    文章结构 如何理解分治算法 分治算法应用举例 1. 如何理解分治算法 1.1 分治算法的核心思想 分治算法的核心思...

  • Leetcode-Java(二十五)

    241. Different Ways to Add Parentheses 采用分治算法,分治算法的基本思想是将...

  • 算法导论第2.3章 - 分治算法

    分治算法 递归:算法一次或多次递归地调用其自身已解决紧密相关的若干子问题。这些算法遵循分治法的思想。 分治算法三个...

  • 算法思想 - 分治算法

    其实相比于分治算法,我更愿意称之为分治“思想”。因为这种思想的应用非常广泛,不仅是在计算机中,在生活中到处都是分治...

  • 09《算法入门教程》分治算法

    1. 前言 本节内容是分治算法系列之一:分治算法的介绍,主要介绍了分治算法的定义及基本思想和实现策略,然后我们介绍...

  • 呕心之作,一篇博客带你精通五大核心算法

    目录 一、分治法 思想原理 具体步骤 例题1 算法结语 二、动态规划算法 思想原理 具体步骤 算法实现 算法结语 ...

  • 分治算法思想

    分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成 n 个...

  • 分治算法

    如何理解分治算法? 分治算法(divide and conquer)的核心思想其实就是四个字,分而治之,也就是将原...

  • 《数据结构与算法之美》32——分治算法

    如何理解分治算法 分治算法(divide and conquer)的核心思想就四个字:分而治之,就是将原问题划分成...

  • 博览网:STL与泛型编程第四周笔记

    简书地址: 1、算法 基本的C++算法分为三类:排序算法、树算法、图算法 算法思想有三种:递推、分治、动态规划 以...

网友评论

      本文标题:算法思想 - 分治算法

      本文链接:https://www.haomeiwen.com/subject/ftigphtx.html