【算法】常用总结

算法 前端之家
前端之家收集整理的这篇文章主要介绍了【算法】常用总结，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
@H_403_65@

分治算法

  • 基本思想：
    分治法(Divide and Conquer)，字面意思就是分而治之，即 将问题简化为“分”和“治”两个步骤。当遇到一个复杂的问题（规模为N），可以根据问题的性质将其分解为两个或者多个规模较小的子问题（加上一共有K个子问题）。

  • 具体操作：
    1. 将复杂问题拆解为子问题；
    2. 将简单子问题求解；
    3. 将子问题的解合并为原问题的解。

  • 适用性：
    通常来说可以适用分治法的问题是问题规模小时容易解决，而且分解后的子问题为性质相同的独立问题。
    在算法题中如果出现了O(logn)的复杂度，都可以先考虑一下分治法。

  • 算法应用：

    快速幂，求\(a^n\)(n为偶数)

    用算法设计的思想，不全部计算出来求3的96次方的第十位数值。

    \(3^{96}=9^{48}=81^{24}=6561^{12}=...\)
    \(A^n=A^{n/2}*A^{n/2}\)，一直递归下去，其间就可以省略很多不必要的计算,得到O（logn）的方法。

贪心算法

  • 基本思想：
    贪心算法(Greedy algorithm)，该算法的名字很形象地说明该算法的特点，将问题分为一个个局部子问题之后，求解每个子问题的时候，不考虑子问题当前的解对于整个问题的影响，只考虑当前情况的最优解，即 当前子问题的解不会对后序的状态造成影响。

  • 具体操作：
    1. 将复杂问题分解为多个子问题；
    2. 子问题的解是当前所有解中的最优解；

    3. 将所有子问题的解合并为原问题的解。

      注意：贪心算法与动态规划算法较为相似，其中一个很关键的区别是贪心算法是不可取消的，自顶向下地求出子问题的当前最优解；而动态规划是每步做出的选择都依赖于子问题的解。

  • 适用性：

动态规划

  • 基本思想：
    动态规划算法与之前的分治和贪心算法有点相似，都是将一个规模大的问题转化为几个小的问题，通过解决小问题来得到整体的解。动态规划的核心问题是问题的状态的定义与状态转移房产的求解。动态规划的关键就在于将重复出现的子问题在第一次求解之后就将其保存起来，以后再遇到时不用重复求解。动态规划是按照自底向上的方式计算最优解。

  • 具体操作：
    1. 将问题分解为不同的子问题；
    2. 定义状态找出初始状态；
    3. 状态转移方程的求解；
    4. 求出问题最终答案。

  • 适用性：
    当题目求解的是最大值/最小值，可行与否或者方案总数时，考虑使用动态规划算法。

回溯算法

  • 基本思想：
    回溯算法通常用于解决复杂的，规模大的问题。回溯算法使用的是深度优先搜索(DFS)的策略。
    所有的可能情况（即 解空间）构成一个搜索树，我们从根结点开始，按照问题的搜索条件向下进行结点选择，在当前结点如果满足解的条件时，就继续向下探索，如果不满足解的条件，那么就回溯到当前结点的父结点，选择另一条路径再继续搜索下去。

  • 具体操作：
    1. 针对所给的问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解；
    2. 确定结点的扩展搜索规则；
    3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

  • 适用性：
    适用于解决复杂的，规模大的问题。

猜你在找的算法相关文章

计算斐波那契数（java）
计算斐波那契数 【lintcode】366 描述 查找斐波纳契数列中第 N 个数。 所谓的斐波纳契数列...
二分搜索树
1.二分搜索树特点：每个节点的键值大于左孩子； 每个节点的键值小于右孩子；以左右孩子为根...
Java算法（一）
【程序1】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到...
O(n*logn)级别的算法之二（快速排序）的三种实现方法详解及其与归并排序的对比
一，单路快排1.测试用例： 2.归并排序： 3.优化时要用的插入排序： 4.单路快排实现： 图解...
Java 算法(二)
【程序9】 题目：一个数如果恰好等于它的因子之和，这个数就称为"完数"...
选择排序的实现以及性能测试
用C++语言实现选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是...
LeetCode283移动零问题java高效解法
一、题目： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素...
链表常见的题型（java实现）
链表是面试中最常见的一种题型，因为他的每个题的代码短，短短的几行代码就可以体现出应聘...
冒泡排序的实现和优化及其与插入，选择排序的比较
备注：这里使用的插入排序和选择排序都是经过优化后的详细优化请查看上一条博客，编译器使...
四个O(n^2)级别的排序性能测试
测试环境为DEV-C++，并且选择排序，插入排序，冒泡排序，均为优化后的，若想了解具...
算法设计模式多媒体技术正则表达式ElasticsearchFlinkHadoopIDE
受约束摘*day25Java常用类库置信lamda留存持续录入年后正则表达式303.17regularexpre匹多模适20130322基础理论pathmunge涵义reectok需要转义的特资源分享validationex简明魔法里弄形如源码实现完备actionscript
分治算法 贪心算法 动态规划 回溯法
问题类型 通用问题 优化问题 优化问题 通用问题
子问题结构 独立，类型相同 只考虑当前子问题 子问题可能重复 无
子问题在最优解里 全部 部分 全部 无
选择与求解次序 先选择后解决子问题 先选择后解决子问题 先选择后解决子问题 用深度搜索来解决问题