五大经典算法思想之分治策略

云惠网小编 2021年12月26日13:17:52
评论
1042字阅读3分28秒
摘要

分治策略的基本思想

广告也精彩

在这里插入图片描述

一、分治策略的基本思想

首先将数组对半划分,归结为两个子数组之后进行排序,然后将两个子数组重复划分,排序,最后综合得到一个从小到大排序的数组。

  1. 将原问题规约为规模小的子问题,子问题与原问题具有相同的性质。
  2. 子问题规模足够小时可直接求解。
  3. 算法可以递归实现也可以迭代实现。
  4. 可以使用递推方程式分析算法的时间复杂度。

1.核心思想

最好的情况下:只需进行一次查找就能得到我们想要的结果。

  1. 将原始问题划分为规模较小的子问题。
  2. 迭代或者递归求解每一个子问题。
  3. 将子问题的解综合得到原问题的解。

最坏的情况下:

依据分治策略的基本思想,我们需要对T进行划分,使得问题规模变小,因为我们将T对半划分 (a+b)/2 向下取整,得到数组的中位数下标m,如果此时x正好是我们找到的中位数m,则输出下标m,如果x比中位数小,则转变为在前半个数组中查找,否则在后半个数组中查找,一直迭代到查找到数x,则输出对应下标,否则输出0。

显然,二分查找是一种典型的采用分治策略设计思想的算法。

  1. 将数x与中位数进行比较,将原问题转化为规模减半的子问题,若x小于中位数,则子问题在前半个数组查找,否则在后半个数组中查找。
  2. 对子问题继续进行二分查找。
  3. 当子问题规模为1时,直接比较数(x)和T(m),相等则返回值m,否则返回0。

归并排序:将一组无序的元素按照从小到大进行排序,下面我们来看一段伪代码:

  1. 子问题与原问题性质一致。
  2. 子问题相互独立求解。
  3. 迭代或递归停止时子问题直接求解。

w(n)=w[n/2]+1 可解为:w(n)=[logn]+1(n为log的下标)

二、二分查找

2、设计思想

最坏情况下:

  1. 将原问题划分为规模为n/2的两个子问题。
  2. 继续划分,将原问题划分成规模为n/4的四个子问题,直到子问题规模为1时,划分结束。
  3. 从规模1到规模n/2,陆续归并排好序的两个子数组,归并一次数组扩大一倍,直到达到原数组规模。

w(n)=2w(n/2)+n-1 可解为:w(n)=nlogn-(n+1)

w(1)=0

3、二分查找的时间复杂度分析

注意:

3.归并排序的时间复杂度分析

输入一个数组T,下标从a到b,输入一个数组x,若x在数组T中,输出下表j,否则输出0。

最好情况数组本来就是按照顺序进行排列的,这时我们不需要进行排序。

算法核心用法:查找一个数x是否在一组数中,下面我们来看一段伪代码:

三、归并排序

2.设计思想

在这里插入图片描述

分治策略

四、总结

1、核心用法

本文转自 https://blog.csdn.net/weixin_53779668/article/details/122145530

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论