算法概论笔记 - 大O符号

引入

Fibonacci

指数Version

function fib(n)
if n=0: return 0
if n=1: return 1
return fib(n-1) + fib(n-2)

包含大量重复计算步骤，基本操作次数为n的指数

线性Version

function fib(n)
if n=0: return 0
create an array f[0...n]
f[0]=0, f[1]=1
for i=2...n:
    f[i]=f[i-1]+f[i-2]
return f[n]

对中间计算结果进行存储，基本操作次数为关于n的线性

对数Version

^1
到
^n
在二叉树上需要logn次上升操作

这里用到分治思想，与快速求指数类似。

function power(a, n)
    if(n=0) return 1
    x = power(a, n/2's floor)
    if(n is even)
        then return(x^2)
    else
        return (a*n^2)

通项公式

1. 构造 大O表示法
   各函数规模增长情况

   一些经验规则：

   1. 常系数可以忽略
   2. 当a>b时， 支配
   3. 任何指数项支配任何多项式项，如 支配
   4. 任何多项式项支配对数项，如n支配

   对数的性质（换底公式）：
   
   随着规模n的增大，对数的底对于算法复杂度并无实际贡献，如 = 19.9316, log_3(1, 000, 000) = 12.5754...)
   因此，在大O符号下，基数可以忽略，因此可以简单记为O(logn)

   一些公式

   (2N+1)} 6 = \frac {N^3} 3)
   when k!= 1,
   

   递归

   基本法则

   1. 基准情形：必须总要有某些基准的情形，它们不用递归就能求解
   2. 不断推进：对于那些要递归求解的情形，递归调用必须总能够朝着一个基准情形推进

   在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作