Big O notation 算法复杂度计算方法

文章目录

Big O notation大零符号一般用于描述算法的复杂程度,比如执行的时间或占用内存(磁盘)的空间等,特指最坏时的情形。

常见的算法复杂度

O(1):Constant Complexity 常数复杂度 O(N):线性时间复杂度 O(N^2):N square Complexity 平方 O(N^3):N square Complexity 立方 O(2^N):Logarithmic Complexity 对数复杂度 O(logN) :Exponential Growth 指数 O(n!) :Factorial阶乘

注意:只看最高复杂度的运算

O(1)

        int n = 1000;
        System.out.println(n);

上面两行代码的算法复杂度即为O(1)。

        int n = 1000;
        System.out.println(n);
        System.out.println(n);
        System.out.println(n);

由于只看最高复杂度的运算,所以上面四行代码的算法复杂度也为O(1)。

O(N)

        for (int i = 0; i < n; i++) {
            System.out.println(i);
        }

以上代码复杂度为O(N)。

O(N^2)

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println(j);
            }
        }

这里有两个嵌套的for循环,所以执行最多的次数肯定为两个for循环次数相乘,即N*N(N等于elements长度),所以这个函数的复杂度为O(N^2)。

O(logN)

是不是一看log(对数)就头大,其实没那么复杂,在看例子前我们先复习复习高中知识,什么是log。

如果x的y次方等于n(x>0,且x不等于1),那么数y叫做以x为底n的对数(logarithm)。 记作logxN=y。其中,x叫做对数的底数。

  1. 底数为10时,写为lg;
  2. 底数为e时,称为自然对数写为ln,这个在高等数学中用的很多;
  3. 底数为2时,主要用在计算机中,写为log,也就是不写底数;

所以我们说的logN其实就是log2N。

        for (int i =2; i < n; i*=2) {
            System.out.println(i);
        }

以上算法的的复杂度即为logN,二分查找法(Binary Search)的复杂度也为logN。

O(2^n)

        for (int i = 2; i < Math.pow(2,n); i++) {
            System.out.println(i);
        }

以上算法的的复杂度即为2N,通过递归的方式计算斐波那契数的复杂度也为2N。

O(n!)

        //factorial:阶乘
        for (int i = 2; i < factorial(n); i++) {
            System.out.println(i);
        }

以上算法的的复杂度即为2N,通过递归的方式计算斐波那契数的复杂度也为2N。

时间复杂度对比

时间复杂度

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券