美文网首页
时间复杂度学习笔记

时间复杂度学习笔记

作者: 翻了两次身的咸鱼 | 来源:发表于2018-11-05 10:57 被阅读0次

        一直以来对时间复杂度这个概念理解不透,网上的文章太多,但大多比较难懂。最近在读《大话数据结构》,终于找到一个能看得明白的解释了,好记性不如烂笔头,索性记录一下。
        一般来说,常见的时间复杂度有o(1)常数阶,o(n)线性阶,o(n²)平方阶等。 那么一个算法的时间复杂度是怎么分析出来的呢?先上点概念,下面是推导方法(大O阶方法)

    1.用常数1取代运行时间中的所有加法常数
    2.在修改后的运行次数函数中,只保留最高阶项
    3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

    如此以上三条得到的结果就是上面说的o(1),o(n)等时间复杂度。

    下面直接上代码举例
    1、常数阶o(1)

    public void sum(){
      int sum = 0,int n = 100; //执行一次
      sum = (n+1) * n / 2; //执行一次
      System.print.out(sum); //执行一次
    }
    

    以上这段代码的运行次数函数是f(n)=3(次),根据上面的理论,先把3换成1,这段代码还是执行了3次,并且它并不会因为n的变化而导致执行次数发生改变,然后发现它根本没有最高结项,时间复杂度并没有o(2),o(3)这种说法。所以这个算法的时间复杂度就是o(1)。

    2、线性阶o(n)

    int n = 100;//执行一次
    for(int i = 0;i < n; i++){
      System.print.out(sum); //这行代码一共被执行了100次(由于n是100,所以一共执行n次)
    }
    

    以上这段代码的运行次数函数是f(n)=n+1(次),它会随着n的改变而改变执行次数。时间复杂度是不考虑常量的,所以这段算法的时间复杂度是就是o(n)。

    …未完待续

    相关文章

      网友评论

          本文标题:时间复杂度学习笔记

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