算法

什么是算法

算法(algorithm),在数学(算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。- wiki

算法的性能衡量

为了统一算法的性能衡量标准,我们需要放弃一切变量,放弃具体的数值,而是用一些比较抽象的手段去描述一个算法。简单来说,放弃具体运行时间,重点研究算法的增长

当然,算法其实是数学与工程相结合的东西,这意味着一个高增长的算法并不是一无是处的,因为你的输入n的规模如果很小,那么高增长可能也并不是很危险。所以,你需要两者结合共同思考。

** 基本的符号 **

θ - theta 放弃一切常数以及低阶项

这里记录一下递归树解法 当一颗递归树以每层两个子节点往下延伸到1为止,那么其高度为logn其总子节点之和为n

要用到的基本数学公式

BIG O

f(n) = O(g(n)) 例子 2n^2 = O(n^3)

含义

  • 两边并不相等
  • 初略的说表示小于等于
  • f(n) 属于 g(n)构成的函数集
  • 可以说 2n^2属于 n^3构成的一个函数集

用法

  1. 宏 f(n) = n^3 + O(n^2) 含义为 f(n)主要是 n^3 但是有一些至多为n^2的误差项 ,可以被认为是上下界描述
  2. 当在左边的时候,他代表的是is n^2 + O(n) = O(n^2)

Omega

Omega符号一般用来描述最优情况

f(n) = Ω(g(n)) 例子 √ ̄n = Ω(lgn) 当n充分大的时候,前面的永远是后面的常数倍

含义

  • 两边并不相等
  • 粗略的说表示大于等于

BIG Theta

Θ 其实就是类似世界的等于符号,上面分别是小于等于,大于等于,这个就是等于符号

small Omega and O

ω 大于

o 小于

解递归式

解递归式的方法有很多种,到目前还没有通用的方法

只学会了一种递归树方法,利用其递归式来分解,并把每一层级加起来

递归树方法

function pusu(x, n) {
  function _pusu(n) {
    if (n === 1) { return x }

    let half
    let res

    if (n % 2 === 0) {
      half = _pusu(n / 2)
      res = half * half
    } else {
      half = _pusu((n - 1) / 2)
      res = half * half * x
    }

    return res
  }
  return _pusu(n)
}