【算法】什么是算法

算法是完成某个特定任务的过程。 通常数据结构作为工具来辅助进行算法, 所以有了一个流传甚广的公式: 程序 = 数据结构 + 算法

  • 算法不是数学, 但是可以用数学来描述
  • 我们要做一件事情, 整个过程本身就是算法
  • 我们最常用的增删改查是算法的一部分
  • 算法可以用自然语言、 流程图、 伪代码和计算机语言等手段来表示
  • 在面向对象语言中, 算法通常通过类的方法实现

算法的特征

算法的五大特征:

  • 有穷性: 算法必须能在执行有限个步骤后终止
  • 确切性: 每一步骤必须由确切的定义
  • 输入项: 有0个或多个输入, 用来规定初始情况, 所谓0 个输入是指算法本身定出了初始条件
  • 输出项: 有一个或多个输出, 是对输入数据处理后的结果。 没有输出的算法毫无意义
  • 可行性: 算法执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,每个计算步骤都可以在有限时间内完成(也称之为有效性。)

如何衡量算法的好坏

  • 算法的好坏主要通过算法复杂度来衡量
    • 时间复杂度
    • 空间复杂度
  • 正确性
  • 可读性
  • 健壮性

常见的复杂度

  • 常数阶 O(1)
  • 对数阶 O(logN)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogN)
  • 平方阶 O(n^2)
  • 立方阶 O(n^3)
  • k次方阶 O(n ^ k)
  • 指数阶O(2 ^ n)

复杂度

计算复杂度

logN 就是类似循环操作的逆运算,每次计算都将计算量减少一半

  • 随着问题规模 n 的不断增加, 时间复杂度不断增大, 算法的执行效率越低
  • 一般做算法复杂度分析的时候, 遵循下面的技巧:
    • 有几重循环, 一般来说就是O(n), 两重就是O(n^2), 依此类推
    • 如果有二分, 则为O(logN)
    • 保留最高项, 去除常数项

计算例子
2019-06-08-23-13-24

你的支持将鼓励我继续创作