一.算法的数学基础

一.算法相关的数学公式

  1. 换底公式:(log_AB=frac{log_cB}{log_CA})
    证明:设(z=log_AB, x=log_cB,y=log_CA),则(A^Z=B,C^X=B,C^Y=A =>{C^Y}^Z=C^X=>YZ=X,)所以(z=frac{X}{Y}),即(log_AB=frac{log_cB}{log_CA})
  2. 模同余定理
    (1)两个数A与B,如果他们除以C后的余数相同,则称A和B模同余。记为(Aequiv B(mod N))
    (2)模同余的条件也可记为:A与B的差整除C
  3. 级数公式
    (1)(sumlimits_{i=0}^{n}2^i=2^{n+1}-1)
    (2)(sumlimits_{i=0}^{n}A^i=frac{A^{n+1}-1}{A-1})
    (3)当公式2中,(0<A<1),则(sumlimits_{i=0}^{n}A^ileq frac{1}{1-A})

二. 函数相对增长率

  1. 相对增长率描述了2个函数之间的关系,是函数间的相对级别
  2. 函数关系的4个定理:
    (1)定理1:有2个函数(T(N))(f(N)),若存在正数c和(n_0),使得当(Ngeq n_0)时,(T(N) leq cf(N)),则称(T(N)=O(f(n)))
    (2)定理2:有2个函数(T(N))(f(N)),若存在正数c和(n_0),使得当(Ngeq n_0)时,(T(N) geq cf(N)),则称(T(N)=Omega(f(n)))
    (3)定理3:若两个函数(T(N))(f(N))之间的关系是(T(N)=Omega(f(n)))(T(N)=O(f(n))),则称(T(N)=Theta(f(n)))
    (4)定理4:有2个函数(T(N))(f(N)),若存在正数c和(n_0),使得当(N> n_0)时,(T(N)<cf(N)),则称(T(N)=o(f(n)))
  3. 要证明(T(N)=O(f(n))),通常不需要证明过程,而是利用一些已知的结果。当(T(N)=O(f(n)))时,可以保证(T(N))在以不快于(f(n))的速率增长
  4. 我们可以通过计算极限(limlimits_{N ightarrow+infty}frac{f(N)}{g(N)})来确定2个函数的相对增长率

三.运行时间计算

  1. 算法的运行时间是一种粗略估计,是对(O(f(n)))的估计值。因此,产生了一些估计算法运行时间的法则
    (1)for循环运行时间:for循环内部语句的运行时间乘以循环次数
    (2)顺序语句运行时间:将各个语句的执行时间求和。eg:(O(n^2)+O(n)=O(n^2))
    (3)if/else语句:if(condition){s1}else{s2} 运行时间为condition判断时间 + s1/s2语句执行的时间
    (4)递归函数的时间复杂度
原文地址:https://www.cnblogs.com/72808ljup/p/5403771.html