美文网首页
算法分析

算法分析

作者: 努力学习的CC | 来源:发表于2020-03-24 17:28 被阅读0次

    时间复杂度为常数的操作:

    1. 给对象赋值

    2. 执行算数运算

    3. 比较大小

    4. 通过索引访问

    5. 调用函数

    6. 函数返回

    我们把一个算法和一个函数f(n)联系起来,从而可以更好的帮助我们分析算法的复杂度。  常见的函数类型有:

    1. 常数函数 f(n)= c,上面说的

    2. 对数函数 x = logbn,二分

    3. 线性函数  f(n)= n,遍历

    4.nlogn函数

    5. 二次函数

    6. 三次函数甚至更高次

    7. 指数函数

    常数函数 <对数函数<线性函数<nlogn函数<二次函数<三次函数<指数函数 

    练习:假设某个算法在输入大小为n的计算时间为T(n)=3*2^n,在一台电脑上跑该算法用了t秒,现在用一台快64倍的计算机运行该算法,在同样的时间t内,能够处理的数据规模大小?

    旧:T(n)=3*n^2

    新:T(n)=64*3*2^n = 3*2^{n+6}

    那么旧的电脑在t秒内处理了n个数据

    n = log_2(\frac {t}{n})

    新的电脑就可以处理:

    t = 3*2^{n+6}

    n+6 = log_2(\frac {t}{n})

    所以可以处理n+6个文件就比旧电脑多处理了6个

    vvvvvvvvvvvvvvvvv   

    相关文章

      网友评论

          本文标题:算法分析

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