时间复杂度的计算

Big O notation

常见的复杂度

O(1)：常数复杂度，这是常数级的运算，不管是O(1)、O(2)、O(3)都为O(1)

public class Test {
    public static void main(String[] args) {
        int n=100;
        System.out.println("n="+n);
    }
}

O(n)：线性时间复杂度，都是从0到n；不管n是多少，都得要循环n次。

public class Test {
    public static void main(String[] args) {
        int n=100;
       for (int i=0;i<n;i++)
           System.out.println("i="+i);
    }
}

O(n^2)：平方。与O(n)类似，里层和外层都得循环n次。

public class Test {
    public static void main(String[] args) {
        int n=100;
       for (int i=0;i<n;i++)
           for (int j=0;j<n;j++)
               System.out.println("i="+i+"\n"+"j="+j);
    }
}

O(n^3)：立方。与O(n)、O(n^2)类似，三层都得是循环n次

O(log n)：对数复杂度。循环不是n次，终止条件改成相应的对数。

public class Test {
    public static void main(String[] args) {
        int n = 100;
        for (int i=1; i<n; i=i*2)
            System.out.println("i=" + i);
    }
}

O(2^n)：指数

public class Test {
    public static void main(String[] args) {
        int n = 100;
        for (int i = 1; i <=Math.pow(2,n); i=i*2)
            System.out.println("i=" + i);
    }
}

只看最高复杂度的运算

递归的时间复杂度，可以试着把一个数带进去，看看需要计算多少次。就可以得出大概的时间复杂度了。在计算时也可以代用定理，主定理(master theorem)

这是从百度百科粘贴过来的，当然如果放做平时面试什么的这些公式也用不到，因为计算起来太过麻烦，这是常用的一些算法的时间复杂度，面试的时候一般不会超过这些。