# 算法系列

# 算法是什么

  • 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制
  • 算法是针对某种问题的解决方案,对于给定输入,在规定要求内得到输出
  • 一个算法的优劣程度可以用空间复杂度与时间复杂度来衡量
  • 不同的算法有自己的特点,可能用不同的时间、空间、效率来解决问题,使用什么算法取决于你的需求

# 为什么学习算法

  • 学习算法可以培养逻辑思维能力,对于程序员来说逻辑思维能力强,在写的代码中bug就越少,考虑的更周全
  • 写出更加高效的代码,算法就是用来解决特定问题的准确方式,这样就避免绕弯路的可能
  • 算法修炼的是一个人的基础功底,学好算法可以更加深入了解计算机,我们不能局限于使用层面,要深入原理,才会真正领悟其真谛
  • 算法最初出现在数学领域,而如今蔓延到计算机领域,对于算法的了解,我们还能更深入的理解编程,把实际问题用计算机语言来实现解答,结合计算机高速的计算能力,可以突破限制人类大脑的瓶颈
  • 在未来人工智能、大数据时代,算法的重要性会更加明显

# 算法的评定

  • 时间复杂度T(n)=O(f(n)),算法的时间复杂度是指执行算法所需要的计算工作量,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关
  • 空间复杂度,算法的空间复杂度是指算法需要消耗的内存空间

# 算法使用的方法

  • 递推法
    • 递推是序列计算机中的一种常用算法
    • 它是按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定项的值
    • 比如斐波那契数组,通过前面的项推出后面的项
  • 递归法
    • 程序调用自身的编程技巧称为递归(recursion)
    • 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解
    • 递归需要有边界条件、递归前进段和递归返回段
    • 当边界条件不满足时,递归前进;当边界条件满足时,递归返回
    • 递归就是在过程或函数里调用自身;
    • 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
  • 穷举法
    • 穷举法,或称为暴力破解法
    • 对于要解决的问题,列举出它的所有可能的情况,逐个判断有哪些是符合问题所要求的条件,从而得到问题的解
    • 比如密码破译,MD5加密算法,对于相同的字符串得出的结果相同,如果有人记录所有长度不超过10的字符串的所有密文,构建一个字符串与密文的映射表,那么如果你使用的字符串在10个字符以内,那么通过暴力破解获得的映射表就能直接查出加密前的字符串
  • 贪心算法
    • 贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术
    • 用贪心法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况
    • 它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题
    • 每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的
  • 分治法
    • 分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题
    • 直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并
    • 一个问题可以划分为若干个相同的子问题,且到最后可以简单的判断出子问题的解。而且其子问题的解可以合并为该问题的解,子问题之间相互独立
  • 动态规划
    • 用于求解包含重叠子问题的最优化问题的方法
    • 将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解
    • 动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法
    • 动态规划程序设计往往是针对一种最优化问题
  • 迭代法
    • 迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程
    • 让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值
  • 分支界限法
    • 对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索
    • 把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)
    • 在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支
  • 回溯法
    • 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标
    • 但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择
    • 这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”
上次更新: 2020-5-17 18:20:47