美文网首页程序员
算法概论笔记 - 大O符号

算法概论笔记 - 大O符号

作者: 芥丶未央 | 来源:发表于2017-07-20 06:57 被阅读0次

引入

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

![](http://latex.codecogs.com/svg.latex?\begin{pmatrix}F_n \F_{n+1} \\end{pmatrix}=\begin{pmatrix}0 & 1 \1 & 1 \\end{pmatrix}^n\begin{pmatrix}F_0 \F_1 \\end{pmatrix})
![](http://latex.codecogs.com/svg.latex?\begin{pmatrix}0 & 1 \1 & 1 \\end{pmatrix})
^1

![](http://latex.codecogs.com/svg.latex?\begin{pmatrix}0 & 1 \1 & 1 \\end{pmatrix})
^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支配

    对数的性质(换底公式):
    ![](http://latex.codecogs.com/svg.latex?log_ab = \frac {log_cb} {log_ca})
    随着规模n的增大,对数的底对于算法复杂度并无实际贡献,如![](http://latex.codecogs.com/svg.latex?log_2(1, 000, 000) = 19.9316, log_3(1, 000, 000) = 12.5754...)
    因此,在大O符号下,基数可以忽略,因此可以简单记为O(logn)

    一些公式

    ![](http://latex.codecogs.com/svg.latex?\sum_{i=1}^N i^2 = \frac {N(N+1)(2N+1)} 6 = \frac {N^3} 3)
    when k!= 1,![](http://latex.codecogs.com/svg.latex?\sum_{i=1}^N i^k = \frac {N^{k+1}} {k+1})
    ![](http://latex.codecogs.com/svg.latex?\sum_{i=1}^N {\frac 1 i} = log_eN)

    递归

    基本法则

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

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

相关文章

  • 算法概论笔记 - 大O符号

    引入 Fibonacci 指数Version 包含大量重复计算步骤,基本操作次数为n的指数 线性Version 对...

  • 读书笔记:图解算法

    读书笔记:图解算法 算法简介 二分查找 O(log n) 大O表示法 大O表示法 让你能够比较操作数,它指出了算法...

  • 算法复杂度

    一、大O表示法 算法的时间复杂度通常用大O符号表述 大O表示法 : ,n为算法所需要执行的操作数 该表示法的操作数...

  • 学习笔记2020-06-04

    1、大O符号 大O代表上界符号。 2、下界符号 3、小o符号 4、下界符号2 5、阶相等符号

  • 基础算法(查找 , 排序)

    算法分析 渐进符号 - (O , Ω , θ) 查找算法 二分查找 - O(logn) 排序算法 直接插入排序 -...

  • 大O表示法

    一、简介 表示时间的大O符号,是用来描述算法效率的语言和度量单位。大O表示法分析了算法的运行时间如何随列表的增长而...

  • 算法基础-01.算法复杂度的计算-主定理

    主定理的定义 『在算法分析中,主定理(英语:master theorem)提供了用渐近符号(大O符号)表示许多由分...

  • iOS集合类

    算法时间复杂度分析 时间复杂度通常用大 O 符号描述。定义了函数的极限特征,被用于描绘算法效率。O 定义了函数增长...

  • IOS开发_基础概念01

    1、大O符号(Big O notation); 2、 1、大O符号(Big Onotation); 1.1 简介:...

  • 2018-06-07

    算法笔记 1 大O算法 1:O(运算次数):表示运算最糟糕情况下 运算时间,表示算法时间的增速 2数组链表 在链表...

网友评论

    本文标题:算法概论笔记 - 大O符号

    本文链接:https://www.haomeiwen.com/subject/uzvkkxtx.html