经典算法之分治算法

阳光穿透心脏的1/2处 2022-10-31 15:59 283阅读 0赞

分治算法

          • 前言
          • 分治法适用的场景
          • 经典案例：二分查找或折半查找
前言

分治算法是递归算法的一种变体，执行效率却高于递归；主要思想是将将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。二分法及快速排序算法都是运用二分法实现的。

分治法适用的场景
  1. 该问题的规模缩小到一定的程度就可以容易地解决；
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解；
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
经典案例：二分查找或折半查找
  1. public static int BinarySearch

发表评论

表情：
评论列表 （有 0 条评论，283人围观）

还没有评论，来说两句吧...

相关阅读

    相关 算法-分治算法

    一、分治 1、定义：分治，也就是分而治之。 它的一般步骤是： ① 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）

    妖狐艹你老母妖狐艹你老母/ 0 赞/ 221 阅读

    相关 分治算法

    问题描述 在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的L型骨牌覆盖给定的特

    约定不等于承诺〃约定不等于承诺〃/ 0 赞/ 200 阅读

    相关 分治算法

    划分问题：整个问题划分成多个无关联的子问题。 递归求解：递归调用求解各个子问题。 合并问题：合并子问题的解，形成原始问题的解。 -------------------

    港控/mmm°港控/mmm°/ 0 赞/ 301 阅读

    相关 分治算法

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 309 阅读

    相关 分治算法

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题

    港控/mmm°港控/mmm°/ 0 赞/ 322 阅读

    相关 分治算法

    一 分治算法介绍 1 分治法是一种很重要的算法 字面上的解释是“分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……，直

    冷不防冷不防/ 0 赞/ 584 阅读