关于前端:分而治之算法

52次阅读

共计 523 个字符,预计需要花费 2 分钟才能阅读完成。

分而治之

原文链接:https://note.noxussj.top/?source=sifo

什么是分而治之?

在咱们后面有学习过一系列数据结构、以及相干的一些算法,蕴含排序、搜索算法。而本次学习的分而治之它不是数据结构,也不是一种算法,而是算法设计中的一种办法,能够了解为是一种思维。咱们能够利用这种思维去设计很多种算法。

分而治之是将一个问题分成多个和原问题类似的小问题,递归解决小问题,再将后果合并以解决原来的问题。次要分成三个局部,别离是 “ 分 ”、” 递归解决 ”、” 合 ”。


根底案例

场景一

归并排序

  • 分:把数组从两头一分为二
  • 解:递归地对两个子数组进行归并排序
  • 合:合并有序子数组

首先它会把一个大的数组拆分成两个小的数组,再别离对每个小数组又进行拆分成两个小数组,以此类推,最初把单个元素的小数组全副进行合并并排序,最初组成一个大数组从而解决了问题。

归并排序是一个典型的分而治之思维的利用。

场景二

疾速排序

  • 分:选基准,按基准把数组分成两个子数组
  • 解:递归地对两个子数组进行疾速排序
  • 合:对两个子数组进行合并

步骤如同归并排序相似。

场景三

二分搜寻同样具备 “ 分 ”、” 解 ”、” 合 ” 的个性。


原文链接:https://note.noxussj.top/?source=sifo

正文完
 0