如何理解算法

从经济学的角度来看,人类的一切行为都可以视作经济问题,也就是成本问题。而算法的设计正是为了达成一个目的,即做一件事情尽可能付出最低的成本,从计算机的角度则为求一个问题的最优解。高效率的人正是贯彻这一思想,微观到解一道数学题,或者宏观到系统性的完成一项大工程。

什么是算法

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作,所有可能的合法的输入都能产生预期的正确的结果。

重要的特性

  1. 有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成。
  2. 确定性:算法中每一条指令必须有确切的含义,不会产生二义性。并且在任何条件下,算法只有唯一的一条执行路径。
  3. 可行性:一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。
  4. 输入:一个算法有零个或多个输入。
  5. 输出:一个算法有一个或多个输出。

设计的要求

通常设计一个“好”的算法,应考虑达到以下目标。

  1. 正确性:算法应当满足具体问题的需求。
  2. 可读性:算法维护需要利于人的阅读与交流,可读性好有助于人对算法的理解,当然这个可读性好是相对概念,取决于面向的对象,绝大多数情况下不应为了可读性而牺牲效率,不然就本末倒置了。
  3. 健壮性:当输入数据非法时,算法也能适当地做出反应或进行处理,而不会产生无法理解和随机的输出结果。
  4. 效率与低存储量需求:效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决,执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。

常用的思想

主流的八大算法思想为:穷举,递归,递推,分治,贪心,回溯,动态规划,模拟。

    • 分而治之当然很好,但是并不是所有问题都可以,比如质因数分解问题。
    • 递归也很好,一种调用自身的编程技巧,大大减少了代码量。
    • 贪心以局部最优解求取全局最优解,追求的是高效率和近似解,可以理解为动态规划的一种特例。
    • 动态规划的本质是定义状态和状态转移方程,实现则通过递推+Memory(剔除重复计算)的组合。
      • DP 状态
        • 符合「最优子结构」原则:DP 状态最优值由更小规模的 DP 状态最优值推出
        • 符合「无后效性」原则:状态的得到方式,不会影响后续其它 DP 状态取值
      • DP 转移方程
        • 分类讨论,细心枚举

递归与递推
以斐波那契数列为例

递归求解(从未知到已知)

递推求解(从已知到未知)

PS:动态规划的解法

回溯代码框架

动态规划代码框架

解决什么问题

  1. 可计算问题:可计算问题才可设计算法。
  2. 计算密集问题(优化):根据冯·诺依曼体系结构可知,计算机资源应对的两大核心问题为IO密集与计算密集。

可计算问题

假设有一个通用的模型,只要能被这个模型计算的问题,称为可计算问题,否则就是不可计算问题,而这个通用模型就是图灵机

当今计算机算法领域的圣杯:P = NP问题(7大千禧年难题之一)。
P:可在多项式时间内解决。
NP:可在多项式时间内验证 如素数验证。
猜想:一个万能算法可以把NP问题复杂度降到P类问题上来。
目前进度:有一类NP完全问题(NPC问题,常见的比如:蛋白质折叠,快递员问题,质因数分解)属于NP问题,一但其中一个问题能够降到P,则所有问题都能。

算法的定量分析

时间复杂度

复杂度 = 计算宽度 x 计算深度
计算宽度:一个集合中一个元素处理时所消耗的步数上界
计算深度:一个集合中所有元素分层(分级)处理的层数(级数)上界
比如快速排序复杂度 = 宽度(n) x 深度(logmn)

常量级 O(1) 如:HashMap查询
亚线性 O(logmn)
线性 O(n)
对数级 O(nlogmn) 如:1 快速排序,2 动态规划 行军路线 O(nlgn+L) n:节点数 L:线段数
指数级 O($m^{n}$) O($n^{m}$) 如:冒泡排序O($n^{2}$)
阶乘级 O(n!) 如:邮递员问题

空间复杂度

记为S(?)

通常空间和时间是联动的,但是相对来说,空间资源更经济,而且很多时候需要采取空间换时间的策略,所以这里暂时不做讨论。

工具

待补充… …

附:关于算法与数据结构

在应用层面,二者必须从统一的角度来看,这个统一的概念就叫程序。
程序 = 算法+数据结构。对数据结构的增删改查操作都是算法问题。

思维发散1:可以形象的理解为数据是主人,算法是管家(负责打理维护)。主人有很多优质业务,管家也把它们打理的有条不紊,这就是一个有前途的程序。

思维发散2:如果从算法与数据结构的角度看框架MVC分层模式:M是数据结构的逻辑形式,V是数据结构的视觉表现形式,C则是算法。

参考

发布者

Loy Wong

A Programmer.